0-1背包最优解怎么去构造

Question

#include
#define N 5
int w[N]={18,13,15,5,8};
int v[N]={20,13,26,20,70};
int p[N]={-1};
int k=0;
int tb()
{
int i;
for(i=0;i printf("% d",p[i]);
printf("\n");
}
int m (int i,int j)
{
int n=N,s1,s2;
int a=0,b=0;
if(i==n)
if(j>=w[n])
{
p[k++]=i;
return v[n];
}

else return 0;
if(j<w[i])
   return m(i+1,j);
   else
   {
     //p[k++]=i;
        s1=m(i+1,j);
        s2=m(i+1,j-w[i])+v[i];
   }

if(s1>s2)
{
       p[k++]=i;
     return s1;
}

else
{
     p[k++]=i;
      return s2;
}

}
int main()
{
int i,t,C=30;
int k=0;
t=m(0,C);
printf("%d\n",t);
tb();

}

Answer 1

'''c++
#include
#include
#include
#define max(a,b) a>b ? a:b
using namespace std;

struct Node
{
int vi; // 价值
int wi; // 重量
};

int dp[1005];
int main()
{
freopen("in.txt", "r", stdin);
int V, N, i, j;
Node list[102];
while (cin >> V >> N)
{
memset(list, 0, sizeof(list));
memset(dp, 0, sizeof(dp));
for (i = 0; i < N; i++) // 输入
{
cin >> list[i].wi >> list[i].vi;
}
for (i = 0; i < N; i++)
{
for (j = V; j >= 0; j--) // 完全背包更新 j从0->v *** 01背包更新 j从V->0
{
if (j >= list[i].wi) // 如果能装下
{
dp[j] = max(dp[j - list[i].wi] + list[i].vi, dp[j]);
}
}
}
cout << dp[V] << endl;
}
return 0;
}
'''