給定n種物品和一個(gè)背包。物品i的重量是wi佛析，價(jià)值是vi益老，背包的容量為c。問應(yīng)如何選擇裝入背包的物品寸莫，使裝入背包中物品的總價(jià)值最大捺萌？
請(qǐng)用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)
分析：
1、二維數(shù)組代表什么储狭？**a[i][j]表示 可選物品為i…n互婿，容量為j時(shí)的背包中所放物品的最大價(jià)值 **
2捣郊、數(shù)組打底工作：從最后一個(gè)物品開始往前，看最后一個(gè)物品下的容量與物品質(zhì)量的關(guān)系
3慈参、遞推式：
詳解解釋見：動(dòng)態(tài)規(guī)劃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代表編號(hào)為i的商品呛牲，j代表的是剩余容量，范圍0--10驮配，所以申請(qǐng)空間是多申請(qǐng)1個(gè)空間
//a[i][j]表示 可選物品為i…n娘扩，容量為j時(shí)的背包中所放物品的最大價(jià)值
int main(){
for(int j=0;j<=c;j++){ //數(shù)組打底 ，當(dāng)前是最后一個(gè)物品
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--){ //從倒數(shù)第二個(gè)商品往前
for(int j=0;j<=c;j++){
if(j<w[i]) //容量不夠壮锻，無(wú)法放
a[i][j]=a[i+1][j]; //不放的話琐旁，當(dāng)前的價(jià)值就等于后一個(gè)物品的價(jià)值
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]); //輸出最大的價(jià)值
int j=c;
for(int i=0;i<n;i++){
if(a[i][j]!=a[i+1][j]){ //價(jià)值不相同猜绣，就證明放進(jìn)去了物品
printf("%d\t",i);
j-=w[i];
}
}
if(j>=w[n-1]){
printf("%d\n",n-1);
}
return 0;
}
運(yùn)行截圖
