题目：

有n件物品和一个容量为C的背包。（每种物品均仅仅有一件）第i件物品的体积是v[i]，重量是w[i]。选一些物品装到这个背包中，使得背包内物品在整体积不超过C的前提下重量尽量大。

解法：两种思路：

第一种：d(i, j)表示“把第i,i+1,i+2,...n个物品装到容量为j的背包中的接下来的最大总重量”。

d(i, j) = max{d(i+1, j), d(i+1, j-v[i])+w[i]}     前面一项表示不放第i个物品，后面一项表示放第i个物品。

然后取两者之中最大的那个。

#include <iostream>

#include <string>

using namespace std;

const int MAXN = 10000;

int n,	C, v[MAXN], w[MAXN];

int d[MAXN][MAXN];  //d(i, j)表示“把第i,i+1,i+2,...n个物品装到容量为j的背包中的接下来的最大总重量”

int main() {

	cin >> n >> C;

	for(int i = 0; i < n; ++i) {

		cin >> v[i] >> w[i];

	}

	memset(d, 0, sizeof(d));

	for(int i = n; i >= 1; --i) {

		for(int j = 0; j <= C; ++j) {

			d[i][j] = (i == n ?

0 : d[i+1][j]);          //不放第i个物品

			if(j >= v[i]) d[i][j] = max(d[i][j], d[i+1][j-v[i]]+w[i]);  //不放第i个物品跟放第i个物品之间的最大值

		}

	}

	cout << d[1][C] << endl;

	return 0;

}

另外一种：d(i, j)表示“把前 i 个物品装到容量为 j 的背包中的最大总重量”。

d(i, j) = max{d(i-1, j), d(i-1, j-v[i])+w[i]}     前面一项表示不放第i个物品。后面一项表示放第i个物品。

然后取两者之中最大的那个。

#include <iostream>

#include <string>

using namespace std;

const int MAXN = 10000;

int n,	C;

int d[MAXN][MAXN];  //d(i, j)表示“把前 i 个物品装到容量为 j 的背包中的最大总重量”。

int main() {

	cin >> n >> C;

	memset(d, 0, sizeof(d));

	int v, w;

	for(int i = 1; i <= n; ++i) {

		cin >> v >> w;

		for(int j = 0; j <= C; ++j) {

			d[i][j] = (i == 1 ?

0 : d[i-1][j]);  //第i个没放进去

			if(j >= v) d[i][j] = max(d[i][j], d[i-1][j-v]+w);  //不放第i个物品跟放第i个物品之间的最大值

		}

	}

	cout << d[n][C] << endl;

	return 0;

}