动态规划之01背包问题

给定n种物品和一个背包，物品i的重量是w[i]，其价值是v[i]，所有物品的重量和价值都是非负的，背包的容量是C。我们限定每种物品只能选择0个或者1个。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？

解题思路：
最终的目标是在总重量不超过C的前提下，使得总价值最高。在总重量不超过Y（Y<=C）的前提下，我们将前i种物品的总价值所能达到的最高价值定义为value[i][Y] ，由此我们可以得到这个问题的最优解与子问题的最优解相同（最优子结构性质），可用动态规划求解。
由上面的叙述可知：
value[0][Y]=0 0<=Y<=C
value[i][0]=0 1<=i<=n
当w[i]>Y时，value[i][Y]=value[i-1][Y](物品i不能放入背包，所以总价值还是前一个物品放入时的价值。)
当w[i]<=Y时，value[i][Y]=max(value[i-1][Y],value[i-1][Y-w[i]]+v[i]。(value[i-1][Y]表示不能放入，value[i-1][Y-w[i]]+v[i]表示放入进去。然后在这两种情况中选取最大值。先把表填了，这样才能更好理解！表格如下：

接下来我们看看代码：

#include <iostream>
using namespace std;
int value[200][200];
int max(int a,int b);
int KnapStack(int n,int w[],int v[],int x[],int C);
//求最大价值以及是哪些物品被选中 

int main(int argc, char** argv) {
    int maxSum;//最大价值 
    int w[10];//重量数组 
    int v[10];//价值数组 
    int x[10];//选中的数组 
    int n;//物品数量 
    int C;//最大容量 
    cout<<"请输入物品数："<<endl;
    cin>>n; 
    cout<<"请输入背包的最大容量："<<endl;
    cin>>C;
    cout<<"请分别输入物品的重量："<<endl;
    for(int i=0;i<n;i++){
        cin>>w[i];
    }
    cout<<"请分别输入物品的价值："<<endl;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    maxSum=KnapStack(n,w,v,x,C);
    cout<<"最大物品价值为："<<endl;
    cout<<maxSum<<endl;
    return 0;
}

int max(int a,int b){
    if(a>=b){
        return a;
    }
    else{
        return b;
    }
}

int KnapStack(int n,int w[],int v[],int x[],int C){
    for(int i=0;i<=n;i++){
        value[i][0]=0;//value[i][0]=0 
    }
    for(int Y=0;Y<=C;Y++){
        value[0][Y]=0;//value[0][Y]=0
    }
    for(int i=0;i<n;i++){//二层for循环用作创建表 
        for(int Y=0;Y<=C;Y++){
            if(Y<w[i]){
                value[i+1][Y]=value[i][Y]; 
            }//value[i][],i的下标从0开始 
            //不能往背包里面放 
            else{
                value[i+1][Y]=max(value[i][Y],value[i][Y-w[i]]+v[i]);
            } 
        }
    }
    int Y=C;
    for(int i=n-1;i>=0;i--){
        if(value[i+1][Y]>value[i][Y]){
            x[i]=1;
            Y-=w[i];
        }
        else{
            x[i]=0;
        }
    }
    cout<<"选中的物品是："<<endl;
    for(int i=0;i<n;i++){
        cout<<x[i]<<"\t";
    }
    cout<<endl;
    return value[n][C];
}