有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是vi，得到的价值是wi。求解将哪些物品装入背包可以使得价值之和最大。
二维数组的暴力解法，未涉及空间优化。 首先用子问题来定义状态，f[i][j]表示前i个物品放到容量为j的空间总价值最大。f[i][j]这个状态是由i-1推过来的，这里有两种考虑：第i中物品选择还是不选择，如果不选择f[i][j]==f[i-1][j]，如果选择f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] w[i])。 max(f[i-1][j], f[i-1][j-v[i]] w[i])的解释： 第i件物品选择，第i件物品占据的空间是v[i]，价值为w[i]。那么前i-1件物品所占据的空间为j-v[i]，价值为f[i-1][j-v[i]]。而f[i][j]是f[i-1][j]和f[i-1][j-v[i]] w[i]其中较大的一个。
代码部分：
代码语言：javascript复制#include <iostream>
using namespace std;
const int maxn=1010;
int v[maxn], w[maxn];
int f[maxn][maxn];
int n, m; //分别表示物品总数为n 背包容量为m
int main() {
cin >> n >> m;
f[0][0] = 0;
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) {
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]);
}
}
}
int res = 0;
for (int i=0; i<=m; i) {
res = max(res, f[n][i]);
}
return 0;
}
