uva 624 （01背包打印路径）

题意：

给张磁带，可以录c分钟的歌，然后给n首时间为vi的歌，问这张磁带最长可以录多少分钟的歌，并打印。

解析：

磁带长度为背包容量，每首歌为每个物品，歌的长度为物品重量，每首歌价值也为物品重量。

状态转移方程：

dp[ i ] [ j ] = max(dp[ i - 1 ] [ j ], dp[ i - 1 ] [ j - v[i] ] +  v[i])

dp[i][j]表示在磁带长度为j时放入第i首歌的最长时间。

对于第i首歌，若不取，则dp[ i - 1 ] [ j ]；若取，dp[ i - 1 ] [ j - v[i] ] + v[i]。

打印时直接递归。

path[i][j]记录的是当前磁带的长度总和，打印时，若path[i - 1][j]小于path[i][j]，表明插入了v[i]，打印。

void print(int i, int j)
{
    if (i == 0)
        return;
    print(i - 1, path[i][j]);
    if (path[i][j] < j)
        printf("%d ", v[i]);
}

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>

#define LL long long

using namespace std;
const int maxn = 20 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = 4 * atan(1.0);
const double ee = exp(1.0);

int c, n;
int v[maxn];
int dp[maxn][10000];
int path[maxn][10000];

void print(int i, int j)
{
    if (i == 0)
        return;
    print(i - 1, path[i][j]);
    if (path[i][j] < j)
        printf("%d ", v[i]);
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    #endif // LOCAL
    while (scanf("%d", &c) == 1)
    {
        memset(v, 0, sizeof(v));
        memset(dp, 0, sizeof(dp));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &v[i]);
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= c; j++)
            {
                dp[i][j] = (i == 1 ? 0 : dp[i - 1][j]);
                path[i][j] = j;
                if (v[i] <= j)
                {
                    if (dp[i][j] < dp[i - 1][j - v[i]] + v[i])
                    {
                        dp[i][j] = dp[i - 1][j - v[i]] + v[i];
                        path[i][j] = j - v[i];
                    }
                }
            }
        }
        print(n, c);
        printf("sum:%d\n", dp[n][c]);
    }
    return 0;
}