0-1背包问题 动态规划法

代码

#include<iostream>

using namespace std;

int KnapSack(int n,int w[],int v[],int C,int x[]){
int V[100][100];
for(int i=0;i<=n;i++){
        V[i][0]=0;
    }
for(int j=0;j<=C;j++){
        V[0][j]=0;
    }
for(i=1;i<=n;i++){
for(j=1;j<=C;j++){
if(j<w[i-1]) V[i][j]=V[i-1][j];
else{
                V[i][j]=V[i-1][j]>V[i-1][j-w[i-1]]+v[i-1]?V[i-1][j]:V[i-1][j-w[i-1]]+v[i-1];
            }
        }
    }
cout<<"二维表V"<<endl;
for(j=0;j<=n;j++){
//构造的二维表打印
for(i=0;i<=C;i++){
cout<<V[j][i]<<" ";
       }
cout<<endl;
    }

    j=C; //求装入背包的物品
for(i=n;i>0;i--){
if(V[i][j]>V[i-1][j]){
            x[i-1]=1;
            j=j-w[i-1];
        }
else{
            x[i-1]=0;
        }
    }
return V[n][C];
}
int main(){
int w[5]={2,2,6,5,4};
int v[5]={6,3,5,4,6};
int C=10;
int x[5];

for(int i=0;i<5;i++){
cout<<"物品"<<i+1<<" 重量"<<w[i]<<" 价值"<<v[i]<<endl;
    }

int result=KnapSack(5, w, v, C,x);
cout<<"装入情况"<<endl;
for( i=0;i<5;i++){
cout<<"物品";
cout<<i+1<<" ";
cout<<x[i]<<endl;
    }
cout<<"最大价值为";
cout<<result<<endl;;
}