【问题描述】有n个重量分别为{w1，w2，…，wn}的物品，它们的价值分别为{v1，v2，…，vn}，给定一个容量为W的背包。
设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么选中要么不选中，要求选中的物品不仅能够放到背包中，而且重量和为W具有最大的价值。

int n=5，W=10; //5种物品，限制重量不超过10
int w[MAXN]={0，2，2，6，5，4}; //下标0不用
int v[MAXN]={0，6，3，5，4，6};

PS：本题不要求背包必须装满

思路：

• 本题用动态规划进行求解，dp[][]存储当前容量背包的最大价值
• 设计出：递推公式 dp[i][j]:i为当前第i个物品j为当前背包可以容纳的容量（即 剩余容量），
• 当不选中i时：dp[i][j]=dp[i-1][j]，
• 当选中时dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])（即选中补=不选中两种情况的最大值）
• 求取路径（即存取选中的物品和它的价值）：如果dp[i][j]!=dp[i-1][j]即选中了该物否则没有选中用book[]数组进行存储。

源码：

#include<bits/stdc++.h>
using namespace std;
int book[105];
int dp[105][105];
int W[105];
int v[105];
int n, w;
void path() {
	int i = n;
	int j = w;
	while (i >= 1) {
		if (dp[i][j] != dp[i - 1][j]) {
			book[i] = 1;
			j -= W[i];
		}
		else
			book[i] = 0;	
		i--;
	}
	
	for (int i = 1;i <= n;i++) {
		if (book[i] == 1)
			cout << W[i] << " " << v[i] << endl;
	}
}
int main() {
	int maxv = 0;
	cin >> n >> w;
	for (int i = 1;i <= n;i++)
		cin >> W[i];
	for (int i = 1;i <= n;i++)
		cin >> v[i];
	for (int i = 1;i <= n;i++) {// 存放物品
		for (int j = 1;j <= w;j++) {
			if (j < W[i]) {
				dp[i][j] = dp[i - 1][j];
			}
				
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + v[i]);
		}
	}
	path();
}