给定n种物品和一个背包。物品i的重量是wi，价值是vi，背包的容量为c。问应如何选择装入背包的物品，使装入背包中物品的总价值最大？
请用动态规划算法实现
分析：
1、二维数组代表什么？**a[i][j]表示 可选物品为i…n，容量为j时的背包中所放物品的最大价值 **
2、数组打底工作：从最后一个物品开始往前，看最后一个物品下的容量与物品质量的关系
3、递推式：
详解解释见：动态规划0-1背包（详解）
#include<stdio.h>
#define n 5 //5种物品
#define c 10 //背包容量
int w[n]={2,2,6,5,4},v[n]={6,3,5,4,6};
int a[n][c+1]; //i代表编号为i的商品，j代表的是剩余容量，范围0--10，所以申请空间是多申请1个空间
//a[i][j]表示 可选物品为i…n，容量为j时的背包中所放物品的最大价值
int main(){
for(int j=0;j<=c;j++){ //数组打底 ，当前是最后一个物品
if(j<w[n-1]) //容量不够
a[n-1][j]=0;
else
a[n-1][j]=v[n-1];
}
for(int i=n-2;i>=0;i--){ //从倒数第二个商品往前
for(int j=0;j<=c;j++){
if(j<w[i]) //容量不够，无法放
a[i][j]=a[i+1][j]; //不放的话，当前的价值就等于后一个物品的价值
else //能放，但放不放还需判断一下大小
a[i][j]=a[i+1][j]>a[i+1][j-w[i]]+v[i]?a[i+1][j]:a[i+1][j-w[i]]+v[i];
}
}
printf("%d\n",a[0][c]); //输出最大的价值
int j=c;
for(int i=0;i<n;i++){
if(a[i][j]!=a[i+1][j]){ //价值不相同，就证明放进去了物品
printf("%d\t",i);
j-=w[i];
}
}
if(j>=w[n-1]){
printf("%d\n",n-1);
}
return 0;
}
运行截图
