题目描述
有容积为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 背包容积sumwcin>>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<