uva 624-CD

01背包，输出方案

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100009
using namespace std;

int f[maxn];
int num[30];
int g[30][maxn];
int cot[30];

int main()
{
    int n,v;
    int sum;
    while(scanf("%d",&sum)!=EOF)
    {
        scanf("%d",&n);
        memset(f,0,sizeof f);
        memset(g,0,sizeof g);
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        for(int i=1;i<=n;i++)
        {
            for(int v=sum;v>=0;v--)
            {
                if(v-num[i]<0)continue;
                if(f[v]<(f[v-num[i]]+num[i]))
                {
                    f[v]=f[v-num[i]]+num[i];
                    g[i][v]=i;
                }
                else
                {
                    g[i][v]=i-1;
                }
            }
        }
        int ma=0,tmp;
        for(int i=0;i<=sum;i++)
        {
            if(f[i]>ma)
            {
                ma=f[i];
                tmp=i;
            }
        }
        int cnt=0;
        int i=n;
        while(i>=1&&tmp>0)
        {
            while(g[i][tmp]!=i)
                i=i-1;
            cot[cnt++]=i;
            tmp-=num[i];
            i--;
        }
        for(i=0;i<cnt;i++)
            printf("%d ",num[cot[i]]);
        printf("sum:%d
",ma);
    }
    return 0;
}