http://acm.timus.ru/problem.aspx?space=1&num=1244dp，0-1背包問(wèn)題：注意題意要看懂，話(huà)說(shuō)我wa了不知道多少次，看了題解才知道原來(lái)是要求剩余重量的背包問(wèn)題?。?！記錄路徑的dp：
#include<stdio.h>
#include<string.h>
#include<math.h>
int tot,n,a[105],g[100005],p[1000005],q[105];
int main()
{
int i,j,flag,sum;
while (scanf("%d%d",&tot,&n)==2)
{
memset(g,0,sizeof(g));
memset(p,0,sizeof(p));
sum=0;
for (i=1; i<=n ; i++ )
{
scanf("%d",&a[i]);
sum+=a[i];
}
tot=sum-tot;
if (tot<0)
{
printf("0\n");
continue;
}
g[0]=1;
for (i=1; i<=n; i++)
{
for (j=tot-a[i]; j>=0; j--)
if (g[j])
{
if (!g[j+a[i]])
p[j+a[i]]=i;
g[j+a[i]]+=g[j];
}
}
if (g[tot]==0)
printf("0\n");
else if (g[tot]>1)
printf("-1\n");
else
{
j=0;
for (i=n; i>=1 ; i-- )
if (p[tot]==i)
{
q[++j]=i;
tot=tot-a[i];
}
for (i=j; i>1 ; i-- )
printf("%d ",q[i]);
printf("%d\n",q[1]);
}
}
return 0;
}
這些個(gè)經(jīng)驗(yàn)還是要好好積累?。。。☆}意看懂有點(diǎn)難，