1940 - 0-1 背包问题（动态规划）
给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？
在选择装入背包的物品时，对每种物品i只能有两种选择，装入或者不装入，不能装入多次，也不能部分装入。
Input
第一行输入物品的个数n。
第二行输入物品的重量序列w。(中间有空格）
第三行输入物品的价值序列v。（中间有空格）
第四行输入背包容量c。
Output
第一行输出装入背包的物品。（用0和1表示，中间无空格）
第二行输出最大价值。
Examples
Input
3 3 4 5 4 5 6 10
Output
011 11
Solution C
#include <stdio.h> #define max 20 int n,c,w[max],v[max],m[max][max]={0}; void knapsack() { int i,j; for (i=1; i<=n; i++) for (j=1; j<=c; j++) { m[i][j]=m[i-1][j]; if ( j>=w[i-1] && m[i-1][j-w[i-1]]+v[i-1]> m[i][j] ) m[i][j]=m[i-1][j-w[i-1]]+v[i-1]; } } void disp( ) { int i,j; int x[max]={0}; i=n; while ( m[i][c]==m[i-1][c] ) i--; while (i>1) { j=i-1; while (m[i][c]-m[j][c]!=v[i-1] && j>0) j--; x[i]=1; i=j; } for(i=2;i<=n;i++) printf("%d",x[i]); } int main( ) { int i,j; scanf("%d",&n); for (i=0; i<n; i++) scanf("%d",&v[i]); for (i=0; i<n; i++) scanf("%d",&w[i]); scanf("%d",&c); knapsack(); disp(); printf("\n"); printf("%d\n",m[n][c]); return 0; }
Solution C++
#include<iostream> using namespace std; int V[200][200]; int max(int a,int b) { if(a>=b) return a; else return b; } int p(int n,int w[],int v[],int x[],int C) { int i,j; for(i=0;i<=n;i++) V[i][0]=0; for(j=0;j<=C;j++) V[0][j]=0; for(i=0;i<=n-1;i++) for(j=0;j<=C;j++) if(j<w[i]) V[i][j]=V[i-1][j]; else V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]); j=C; for(i=n-1;i>=0;i--) { if(V[i][j]>V[i-1][j]) { x[i]=1; j=j-w[i]; } else x[i]=0; } for(i=1;i<n;i++) { cout<<x[i]; } cout<<"\n"; return V[n-1][C]; } int main() { int s; int w[15]; int v[15]; int x[15]; int n,i; int C; n=5; cin>>n; for(i=0;i<n;i++) cin>>v[i]; for(i=0;i<n;i++) cin>>w[i]; cin>>C; s=p(n,w,v,x,C); cout<<s<<"\n"; }