特别经典的背包01,每一步操作要背下来
`#include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];//保存所有集合最值状态
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ) //下标?便于理解?
cin >> v[i] >> w[i];
for (int i = 0; i <= m; i ) {
f[0][i] = 0;
}
for (int i = 1; i <= n; i ) { //先用有限的件范围内逐步放满背包,再用多一件的件数放满背包
for (int j = 1; j <= m; j ) {
if(v[i] <= j)
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);//能放入新一件物品
else
f[i][j] = f[i - 1][j];
}
}
cout << f[n][m];
return 0;
}`