#include
#include
int dp[10000][10000];
int w[10000];
int v[10000];
int o[10000];
//找最大值
int max(int a,int b){
if(a>=b){
return a;
}
else
return b;
}
//制表
int biao(int (*dp)[10000],int*w,int*v,int j,int n)
{
for(int a=0;a<=j;a++){
dp[0][a]=0;
}
for(int a=0;a<=n;a++){
dp[a][0]=0;
}
for(int g=1;g<=n;g++){
for(int h=1;h<=j;h++){
if(j-1][h];
}
else
{
dp[g][h]=max((dp[g-1][h]),(dp[g-1][h-w[g]]+v[g]));
}
}
}
}
//找装了哪些物品
int zhui(int*o,int (*dp)[10000],int *w,int n,int j)
{
for(int i=n;i>=1;i--){
if(j>=w[i]&&(dp[i][j]==(dp[i-1][j-w[i]]+v[i])))
{
o[i]=1;
j-=w[i];
}
else
{
o[i]=0;
}
}
}
//主函数
int main()
{
int j,n;
w[0]=0;
v[0]=0;
scanf("%d",&j);
scanf("%d",&n);
for(int y=1;y<=n;y++){
scanf("%d",&w[y]);
}
for(int z=1;z<=n;z++){
scanf("%d",&v[z]);
}
biao(dp,w,v,j,n);
zhui(o,dp,w,n,j);
for(int f=1;f<=n;f++){
if(o[f]==1){
printf("%d ",f);
}
}
//总的重量和价值
int zw=0,zv=0;
for(int l=1;l<=n;l++){
if(o[l]==1){
zw+=w[l];
zv+=v[l];
}
}
printf("%d %d",zw,zv);
}


写了一个动态规划解01背包的代码,但答案一直是错的,有佬知道是哪错了吗?