一个大佬的写法:
#include<bits/stdc++.h> using namespace std; const int MAXN = 1005; int v[MAXN]; // 体积 int w[MAXN]; // 价值 int f[MAXN][MAXN]; // f[i][j], j体积下前i个物品的最大价值 int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { // 当前背包容量装不进第i个物品,则价值等于前i-1个物品 if(j < v[i]) f[i][j] = f[i - 1][j]; // 能装,需进行决策是否选择第i个物品 else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]); } cout << f[n][m] << endl; return 0; } 作者:深蓝 链接:https://www.acwing.com/solution/content/1374/ 来源:AcWing 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
标签:std,01,int,问题,背包,MAXN,体积 From: https://www.cnblogs.com/daitu66/p/17729001.html