01bag-AGL.zip_knapsack c

#include<stdio.h> int b[100][200]; int V[100][200]; int A[1001]; int mi[1001],vi[1001]; int sum=0; int print(int i,int w) { if(i==0||w==0) return 0; if(b[i][w]==2) { print(i-1,w-mi[i]); // printf("%d",i); sum++; A[sum]=i; } else print(i-1,w); return 0; } int main() { int n,m; int i,w; scanf("%d%d",&n,&m);//numbers&sd for(i=1;i<=n;i++) scanf("%d",&mi[i]); for(i=2;i<=n;i++) scanf("%d",&vi[i]); for(w=0;w<=m;w++) V[0][w]=0; for(w=0;w<mi[1];w++) V[1][w]=0; for(w=mi[1];w<=m;w++) V[1][w]=vi[1]; for(i=1;i<=n;i++) for(w=0;w<=m;w++) if(mi[i]>w) { V[i][w]=V[i-1][w]; b[i][w]=1;//1="up" } else if(V[i-1][w]>V[i-1][w-mi[i]]+vi[i]) { V[i][w]=V[i-1][w]; b[i][w]=1;//1="up" } else { V[i][w]=V[i-1][w-mi[i]]+vi[i]; // sum++; b[i][w]=2;//2="up7" } // printf("%d\n",sum); print(n,m); printf("%d\n",sum); for(i=1;i<=sum;i++) printf("%d ",A[i]); return 0; }