#include<iostream> #include<algorithm> using namespace std; int w[21]={0}; int v[21]={0}; int flag[21]={0}; int arr[21][1024]={0}; int main() { int n=0,c=0; scanf("%d%d",&n,&c); for(int i=1;i<=n;i++) { scanf("%d",&w[i]); } for(int i=1;i<=n;i++) { scanf("%d",&v[i]); } for(int i=1;i<=n;i++)//物品i { for(int j=1;j<=c;j++)//重量j { if(j>=w[i]) { arr[i][j]=max(arr[i-1][j],arr[i-1][j-w[i]]+v[i]); } else arr[i][j]=arr[i-1][j]; } } printf("%d ",arr[n][c]); int h=n,g=c; while(h>=1) { if(arr[h][g]==arr[h-1][g])flag[h]=0; else { flag[h]=1; g=g-w[h]; } h--; } for(int i=1;i<=n;i++) { printf("%d",flag[i]); } return 0; }使用C语言替换

#include<stdio.h>

int w[21]={0};
int v[21]={0};
int flag[21]={0};
int arr[21][1024]={0};

int main() {
int n=0,c=0;
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++) {
scanf("%d",&w[i]);
}
for(int i=1;i<=n;i++) {
scanf("%d",&v[i]);
}
for(int i=1;i<=n;i++) {//物品i
for(int j=1;j<=c;j++) {//重量j
if(j>=w[i]) {
arr[i][j]=arr[i-1][j]>arr[i-1][j-w[i]]+v[i]?arr[i-1][j]:arr[i-1][j-w[i]]+v[i];
}
else arr[i][j]=arr[i-1][j];
}
}
printf("%d ",arr[n][c]);
int h=n,g=c;
while(h>=1) {
if(arr[h][g]==arr[h-1][g])flag[h]=0;
else {
flag[h]=1;
g=g-w[h];
}
h--;
}
for(int i=1;i<=n;i++) {
printf("%d",flag[i]);
}
return 0;
}