朴素的 动规的 基本表示：
f[ i ] [ j ] : 表示只看前 i 个物品，总体积是 j 的情况下，总价值最大是多少
result = max[ f [ n ] [ 0 ~ V ] ]
f[i] [j] =
1.不选第 i 个物品： f[i] [j] = f[i - 1] [j];
2.选第 i个物品： f[i] [j] = f[i - 1] [j - v[i]];
f[i] [j] = max{1,2}
例题
//板子板子 #include <bits/stdc++.h> using namespace std; const int N = 1010; int n,m; int f[N][N]; int v[N],w[N]; int main() { cin >> n >> m; //小白想检验一下生成的f数组是不是全0数组 // for(int j = 0;j < n;j++) cout<<f[j][4]; for(int i = 1;i <= n;i++) { cin >> v[i] >> w[i]; } //下面这个循环是 依次考虑 当第i个物品时，体积j依次增大，直到大于v[i]时，即当前可以装下第i个物品，即拥有了第i个物品的价值。下面进行降维优化时，j从最大体积m依次减小考虑情况。 for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { f[i][j] = f[i - 1][j]; if(j >= v[i]) { f[i][j] = max(f[i][j],f[i - 1][j - v[i]] + w[i]); //小白手动跑了一遍检验发现 f[n][m]已经是最大的价值 因为赋值时进行了选择 } } } // int res = 0; // for(int i = 0;i <= m;i++) // { // res = max(res,f[n][i]); // } cout<<f[n][m]<<endl; return 0; }
#include <bits/stdc++.h> using namespace std; const int N = 1010; int n,m; int f[N]; //这里进行降维优化 int v[N],w[N]; int main() { 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 = m;j >= v[i];j--) { //由于此时变成了一位数组 由于比较的是和它前一位f[i-1][j-v[i]]为了更好地表示发生变化，我们应选择体积从最大的体积m依次递减 f[j] = max(f[j],f[j - v[i]] + w[i]); } } cout<<f[m]<<endl; return 0; }
