您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

UVA 624 CD - 0/1 背包輸出方案

編輯：C++ 入門

題目大意

磁帶長度 N 分鐘，m ≤ 20 首曲目，長度 v_i。
選擇若干曲目（保持原序）使總長 ≤ N 且盡可能大。輸出選中的曲目長度與總和。

解法：0/1 背包 + 路徑記錄

狀態定義

dp[j]：容量 j 最大總長。
path[i][j]：考慮前 i 首曲目、容量 j 時，第 i 首是否選中 (0/1)。

轉移

for i = 0..m-1:
    for j = N..v[i]:
        if dp[j] < dp[j-v[i]] + v[i]:
            dp[j] = dp[j-v[i]] + v[i]
            path[i][j] = 1
        else path[i][j] = 0

回溯輸出

j = N
for i = m-1 .. 0:
    if path[i][j] == 1:
        print v[i]
        j -= v[i]
print "sum:", dp[N]

完整程式碼

#include <cstdio>
#include <cstring>
#define N 10005

int dp[N], path[25][N], v[25];

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        for (int i = 0; i < m; i++) scanf("%d", &v[i]);
        memset(dp, 0, sizeof dp);
        memset(path, 0, sizeof path);
        for (int i = 0; i < m; i++)
            for (int j = n; j >= v[i]; j--)
                if (dp[j] < dp[j-v[i]] + v[i]) {
                    dp[j] = dp[j-v[i]] + v[i];
                    path[i][j] = 1;
                }
        int j = n;
        for (int i = m-1; i >= 0; i--)
            if (path[i][j]) {
                printf("%d ", v[i]);
                j -= v[i];
            }
        printf("sum:%d\n", dp[n]);
    }
    return 0;
}