以 UVA 624 CD 为例，题为简单的01背包，重点看路径的记录部分。
代码1：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=100010;
int dp[maxn],path[maxn],ans[maxn],w[maxn];
int main()
{
int V,n,i,j,cnt;
while(~scanf("%d",&V))
{
{
cnt=0;
fill(path,path+maxn,-1);
fill(dp,dp+maxn,0);
}
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&w[i]);
for(i=1;i<=n;i++)
{
for(j=V;j>=w[i];j--)
{
if(dp[j]<dp[j-w[i]]+w[i])
{
dp[j]=dp[j-w[i]]+w[i];
path[j]=i;
}
}
}
i=dp[V];
while(i>0)
{
ans[cnt++]=w[path[i]];
i-=w[path[i]];
}
for(i=cnt-1;i>=0;i--)printf("%d ",ans[i]);
printf("sum:%d\n",dp[V]);
}
return 0;
}
代码2：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=10000;
int dp[maxn],path[25][maxn],ans[maxn],w[maxn];
int main()
{
int V,n,i,j,cnt;
while(~scanf("%d",&V))
{
{
cnt=0;
fill(path[0],path[0]+maxn*25,0);
fill(dp,dp+maxn,0);
}
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&w[i]);
for(i=1;i<=n;i++)
{
for(j=V;j>=w[i];j--)
{
if(dp[j]<dp[j-w[i]]+w[i])
{
dp[j]=dp[j-w[i]]+w[i];
path[i][j]=1;
}
}
}
j=V;
for(i=n;i>=1;i--)
{
if(path[i][j])
{
ans[cnt++]=w[i];
j-=w[i] ;
}
}
for(i=cnt-1;i>=0;i--)printf("%d ",ans[i]);
printf("sum:%d\n",dp[V]);
}
return 0;
}
原文：https://www.cnblogs.com/VividBinGo/p/11366691.html