二维表示
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 1010; 5 int n,m; //个数和背包容量 6 int v[N],w[N]; //每个物品的体积和价值 7 int f[N][N]; //表示状态 8 9 int main() 10 { 11 cin >> n >> m; 12 13 for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; //读入所有的物品 14 15 // f[0][0 ~ m] = 0; //0个没有意义,且全局变量已经初始化 16 17 //f[i][j] 表示从1~i的数,总价值不超过j的集合 18 for (int i = 1; i <= n; i ++ ) //枚举个数 19 for (int j = 0; j <= m; j ++ ) //枚举体积 20 { 21 f[i][j] = f[i - 1][j]; 22 if(j >= v[i]) f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]); //判断是否为空集 23 } 24 cout << f[n][m]; 25 26 return 0; 27 }