一、题意

给一个V（V<=10000）和一个n（n<=20），V代表磁带的最大长度，n表示n首曲子，然后给出每首曲子的长度，现在要求你选一些曲子放入磁带中，使得磁带的利用率最高，输出最终磁带中存放的曲子序列，并输出总长度。

二、解析

换了个皮也得认出这是一个01背包问题。翻译过来就是：
往体积为V的背包里放物品，n个物品的体积给出，在本题中体积也是价值，然后尽可能使背包里物品的总价值最大。
直接套用01背包问题的转移方程：dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - v[i]] + w[i])
在本题中体积就是价值，所以即为 dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - a[i]] + a[i])
dp[i][j]表示从第i个物品开始的之后的物品放入体积为j的背包中的最大价值

打印路径我还是比较喜欢递归打印的方法。见代码。

三、代码

#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 20 + 5, maxv = 10000 + 5;
int V, n, a[maxn], dp[maxn][maxv];

void print_ans(int i, int j) {
    if(i == n) return;
    if(dp[i][j] == dp[i + 1][j - a[i]] + a[i]) {
        cout << a[i] << " ";
        print_ans(i + 1, j - a[i]);
    }
    else print_ans(i + 1, j);
}

int main() {
    while(cin >> V >> n) {
        for(int i = 0; i < n; i ++) cin >> a[i];

        for(int j = 0; j <= V; j ++) dp[n][j] = 0;
        for(int i = n - 1; i >= 0; i --) {
            for(int j = 0; j <= V; j ++) {
                dp[i][j] = dp[i + 1][j];  // 不选
                if(j >= a[i] && dp[i + 1][j - a[i]] + a[i] > dp[i][j]) {  // 选
                    dp[i][j] = dp[i + 1][j - a[i]] + a[i];
                }
            }
        }
        print_ans(0, V);
        cout << "sum:" << dp[0][V] << endl;
    }
}

四、归纳

  • 01背包问题：即将n个物品放入容量为V的背包中， 每个物品只有一个，要么选要么不选。
    • 转移方程：dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - v[i]] + w[i])
    • dp[i][j]表示从第i个物品开始的之后的物品放入剩余体积为 j 的背包中的最大价值