HIGH87 【模板】多重背包

题目描述

有 种物品和一个容量为 的背包。第 种物品的体积是 ，价值是 ，并且数量最多有 件。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

解题思路

这是一个经典的多重背包问题。它介于0-1背包（每种物品只有1件）和完全背包（每种物品有无限件）之间。

最朴素的想法是将第 种物品看作 件独立的、体积为 、价值为 的物品，然后直接套用0-1背包的解法。但这种方法在 很大时，总物品数量会急剧增加，导致超时。

更高效的策略是二进制优化（也称二进制拆分），其核心思想是将多重背包问题转化为一个等价的0-1背包问题，同时控制转化后的物品数量。

1. 二进制拆分

我们可以将第 种物品的 件拆分成 件新的“组合物品”。

具体来说，任何一个正整数 都可以用若干个 的幂次之和来表示。例如，如果 ，我们可以将其拆分为 (其中 , )。通过选择这几个数组合，我们可以凑出 到 之间的任意整数。例如：

因此，对于数量为 的第 种物品，我们可以将其拆解为以下几件新的物品：

  • 1件体积为 、价值为 的物品。
  • 1件体积为 、价值为 的物品。
  • 1件体积为 、价值为 的物品。
  • ...
  • 1件体积为 、价值为 的物品，其中 。
  • 1件体积为 、价值为 的物品（如果有剩余）。

通过这种方式，我们将原来的一种物品（可选 次）转换为了大约 种新的物品，而每种新物品最多只能选一次。

2. 0-1背包求解

将所有 种物品都进行二进制拆分后，我们就得到了一个物品列表，其中每件物品都只能选择一次（0-1选择）。现在问题就转化为了一个标准的0-1背包问题。

  • 状态定义： 表示在背包容量为 的前提下，能获得的最大总价值。
  • 状态转移方程：对于拆分后的每一件新物品（体积为 ，价值为 ），我们更新 数组：
  • 循环顺序：为了保证每件新物品最多只被选择一次，我们需要逆序遍历背包容量 （从 到 ）。

算法总结

  1. 创建一个新的空列表，用于存放拆分后的物品。
  2. 遍历原来的每一种物品 。
  3. 使用二进制拆分，将该种物品拆分为多个新的物品，并将它们加入新列表。
  4. 初始化一个大小为 的 数组，所有元素为0。
  5. 遍历新列表中的每一个物品 。
  6. 逆序遍历背包容量 (从 到 )，并根据状态转移方程更新 。
  7. 所有循环结束后， 即为最终答案。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 物品结构体，用于二进制拆分后存储
struct Item {
    int w, v;
};

void solve() {
    int n, m;
    cin >> n >> m;

    vector<Item> items;
    for (int i = 0; i < n; ++i) {
        int w, v, c;
        cin >> w >> v >> c;
        // 二进制拆分
        for (int k = 1; k <= c; k *= 2) {
            items.push_back({k * w, k * v});
            c -= k;
        }
        if (c > 0) {
            items.push_back({c * w, c * v});
        }
    }

    vector<long long> dp(m + 1, 0);

    // 0-1背包
    for (const auto& item : items) {
        for (int j = m; j >= item.w; --j) {
            dp[j] = max(dp[j], dp[j - item.w] + item.v);
        }
    }

    cout << dp[m] << endl;
}

int main() {
    // 多组测试数据，开启IO优化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

public class Main {
    
    // 物品类
    static class Item {
        int w, v;
        Item(int w, int v) {
            this.w = w;
            this.v = v;
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        int m = sc.nextInt();

        List<Item> items = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int w = sc.nextInt();
            int v = sc.nextInt();
            int c = sc.nextInt();

            // 二进制拆分
            for (int k = 1; k <= c; k *= 2) {
                items.add(new Item(k * w, k * v));
                c -= k;
            }
            if (c > 0) {
                items.add(new Item(c * w, c * v));
            }
        }

        long[] dp = new long[m + 1];

        // 0-1背包
        for (Item item : items) {
            for (int j = m; j >= item.w; j--) {
                dp[j] = Math.max(dp[j], dp[j - item.w] + item.v);
            }
        }

        System.out.println(dp[m]);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }
}

import sys

def solve():
    # 读取n和m
    n, m = map(int, sys.stdin.readline().split())
    
    original_items = []
    for _ in range(n):
        original_items.append(list(map(int, sys.stdin.readline().split())))

    items = []
    # 二进制拆分
    for w, v, c in original_items:
        k = 1
        while k <= c:
            items.append((k * w, k * v))
            c -= k
            k *= 2
        if c > 0:
            items.append((c * w, c * v))
            
    dp = [0] * (m + 1)

    # 0-1背包
    for w, v in items:
        for j in range(m, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)
            
    print(dp[m])


def main():
    # 多组测试数据
    t = int(sys.stdin.readline())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

  • 时间复杂度: 假设物品数量为 ，背包容量为 ，第 种物品的数量为 。二进制拆分后，物品总数变为 。之后进行0-1背包求解的复杂度是 。因此，总时间复杂度为 。
  • 空间复杂度: 需要 的空间来存储拆分后的新物品，以及 的空间来存储 数组。因此，总空间复杂度为 。