动态规划0-1背包

---

---

给定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;
}

运行截图