UVA 624 CD （01背包 带路径）

题意 输入两个数 len，n 表示长度和个数，接下来输入n个数， 表示每一个的长度， 求这n个数能够组成的不超过len的最大长度，并输出这些数。

分析：01背包，dp数组非0表示可以组成的数，dp数组用来记录路径

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <stack>
#include <algorithm>

using namespace std;

const int maxn = 2005;

int a[22];
int dp[maxn];

int main()
{
    int len, n;
    while(~scanf("%d%d", &len, &n))
    {
        memset(dp, 0, sizeof(dp));
        for(int i=1; i<=n; i++)
        {
            scanf("%d", &a[i]);
        }
        dp[0] = 1;
        int Max = 0;
        for(int i=n; i>=1; i--)
        {
            for(int j=len; j>=a[i]; j--)
            {
                if(dp[j-a[i]]&&dp[j]==0)
                {
                    dp[j] = a[i];
                }
            }
        }
        while(dp[len]==0)
            len--;
        Max = len;
        while(len)
        {
            printf("%d ", dp[len]);
            len -= dp[len];
        }
        printf("sum:%d
", Max);
    }

    return 0;
}