/* 题目内容： 物品集合U=｛u1,u2…un｝，体积分别为s1,s2……sn，价值分别为v1,v2….vn；容量C的背包。设计算法实现放入背包的物品价值最大。 输入描述 第一行输入物品数n,第二行输入每个物品体积，第三行输入每个物品的价值，第四行输入背包的容量C 输出描述 输出最大价值数。 输入样例 3 3 4 5 4 5 6 10 输出样例 11 */
#include<stdio.h> #define MAX 1000 #define MAXN 20 #define max(a,b) a>b ? a:b int D[MAXN][MAXN]; int FillD(int n,int c,int w[],int v[]){ int i,j; for(i=1;i<=n;i++) for(j=1;j<=c;j++) if(j<w[i]) D[i][j]=D[i-1][j]; else D[i][j]=max(D[i-1][j],D[i-1][j-w[i]]+v[i]); return 1; } int OptLoad(int n,int c,int w[],int v[],int x[]){ int i,j; i=n;j=c; while(i>0) if(D[i][j]==D[i-1][j]){ x[i]=0; i--; } else{ x[i]=1; j-=w[i]; i--; } return D[n][c]; } int main() { int n,i,s,j,a[1000],c[1000],x[1000],ans; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&a[i]); } for(i=1;i<=n;i++){ scanf("%d",&c[i]); } scanf("%d",&s); FillD(n,s,a,c); ans=OptLoad(n,s,a,c,x); printf("%d\n",ans); return 0; }