@[YangJinxi_7_22](/user/505959) 假如直接用 0/1 背包，您怎么做（套了一个分数规划的情况下）？
by _cyle_King @ 2022-08-01 10:17:24
第一篇题解就是01背包
by HeCao2008 @ 2022-08-01 10:17:35
@[HeCao2008](/user/422996) lz的意思应该是直接用朴素的 0/1 背包，没有用二分。
by _cyle_King @ 2022-08-01 10:18:38
@[_cyle_King](/user/582035) 哦哦
by HeCao2008 @ 2022-08-01 10:19:21
@[_cyle_King](/user/582035) 就是以重量为下标，然后用0/1背包找到每个重量对应的最大才艺值，然后再进行判断，虽然有可能超时，但不应该WA吧
by YangJinxi_7_22 @ 2022-08-01 10:27:11
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int N = 255;
const int M = 3e7+5;
int n , W , m;
int w[N] , t[N] , f[M] , g[M];
int main( ) {
cin >> n >> W;
for( int i = 1 ; i <= n ; i++ ){
cin >> w[i] >> t[i];
//g[w[i]] = 1;
m += w[i];
}
g[0] = 1;
for( int i = 1 ; i <= n ; i++ ){
for( int j = m ; j >= 1 ; j-- ){
if( j - w[i] >= 0 ){
f[j] = max( f[j-w[i]] + t[i] , f[j] );
g[j] = max( g[j-w[i]] , g[j] );
}
}
}
double ans = 0;
for( int i = W ; i <= m ; i++ ){
if( g[i] ){
ans = max( ans , (double)((double)(f[i])/(double)(i)) );
}
}
cout << (int)(1000*ans) <<endl;
return 0;
}
```
这个代码就是按0/1背包写的，TLE我可以理解，但是为什么有的点回WA？
by YangJinxi_7_22 @ 2022-08-01 10:28:50
@[YangJinxi_7_22](/user/505959) 建议自己学一下分数规划，这真的不能直接做。最后决策时要让总重量超过 $W$，并且还套了分数规划，这个做法明显有问题（反例自可以举出来）。
by _cyle_King @ 2022-08-01 10:35:28
@[_cyle_King](/user/582035) 如有不对之处，勿喷。
by _cyle_King @ 2022-08-01 10:37:56
@[_cyle_King](/user/582035) 我主要是找不到反例
by YangJinxi_7_22 @ 2022-08-01 10:55:35
@[YangJinxi_7_22](/user/505959) 可以下数据啊，这就是反例。
by _cyle_King @ 2022-08-01 11:37:20