01背包问题（动态规划）

有容积为w的背包，有n个物品，并且已知每个物品的体积和价值，找到一种方法将若干物品放入背包，使背包中物品的总价值最大。输入物品件数n、背包容积w、每个物品的体积和价值，输出可以装入背包中的物品的最大总价值。n不大于15。

在第一行输入物品件数n和背包容积w，在下一行输入n个整数表示n个物品的体积，在第三行输入n个整数表示n个物品的价值。遇到文件末尾结束

在一行输出可以得到的背包中物品的最大总价值。

4 8

2 4 4 3

3 4 3 6

10

#include 
using namespace std;
int main()
{
	int sumk,sumw;//物品件数sumk 背包容积sumw
	cin>>sumk>>sumw;
	int dp[sumk+1][sumw+1];//避免数组从0 0开始出现错误
	memset(dp,0,sizeof(dp));//将最优解全部赋值为 0 
	int weight[sumk],value[sumk];//定义物品重量与价值的数组 
	for(int i=1;i<=sumk;i++)
	{
		cin>>weight[i];
	}
	for(int i=1;i<=sumk;i++)
	{
		cin>>value[i];
	}
	int k,w;//k为物品编号，w为背包容量
	for(k=1;k<=sumk;k++)
	{
		for(w=1;w<=sumw;w++)
		{
			if(weight[k]>w)//物品重量 > 背包容量 第k件物品背包装不了
				dp[k][w]=dp[k-1][w];//找k-1件物品去装 
			else //第k件物品可以装，但要求出装与不装的最优解 
				dp[k][w]=max(dp[k-1][w-weight[k]]+value[k],dp[k-1][w]); 
				//装 物品编号-1，背包容量减对应重量，再加上对应物品价值
				//不装 物品编号-1
		}
	}
	cout<