题解 | #【模板】多重背包#

【模板】多重背包

https://www.nowcoder.com/practice/8fa10063d33a43dd9652c1511a34d461

题目链接

【模板】多重背包

题目描述

给定 $N$ 种物品和一个容量为 $V$ 的背包。第 $i$ 种物品的体积是 $v_i$ ，价值是 $w_i$ ，并且数量最多有 $c_i$ 件。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输入:

第一行输入一个整数 $T$ ，表示有 $T$ 组测试数据。
对于每组测试数据：
- 第一行输入两个整数 $N, V$ ，分别表示物品种类和背包容量。
- 接下来 $N$ 行，每行输入三个整数 $v_i, w_i, c_i$ ，分别表示第 $i$ 种物品的体积、价值和数量。

输出:

对于每组测试数据，输出一个整数，表示能获得的最大总价值。

解题思路

本题是典型的 多重背包问题。它介于01背包和完全背包之间：每种物品可以选择多次，但有数量上限。

朴素解法 (超时):
- 最直接的想法是将每种物品看作 $c_i$ 个独立的、相同的物品，然后用01背包的方法解决。但如果 $c_i$ 很大，物品总数会非常多，导致超时。
二进制拆分优化:
- 我们可以对物品数量 $c_i$ 进行优化。核心思想是，任何一个在 $[1, c_i]$ 范围内的整数，都可以由 $1, 2, 4, 8, \dots, 2^k$ 以及一个余数 $c_i - (2^{k+1}-1)$ 的和来表示。
- 例如，如果一种物品有 $c_i = 10$ 件，我们可以将其拆分为4个新的“物品包”：
  - 数量为 $1$ 的包：体积 $1 \cdot v_i$ ，价值 $1 \cdot w_i$
  - 数量为 $2$ 的包：体积 $2 \cdot v_i$ ，价值 $2 \cdot w_i$
  - 数量为 $4$ 的包：体积 $4 \cdot v_i$ ，价值 $4 \cdot w_i$
  - 数量为 $10 - (1+2+4) = 3$ 的包：体积 $3 \cdot v_i$ ，价值 $3 \cdot w_i$
- 通过选择这几个包的组合，我们可以凑出原物品数量从 $0$ 到 $10$ 的任意件。
- 这样，我们将原来的一种物品（数量为 $c_i$ ）拆分成了 $O(\log c_i)$ 个新的物品，每个新物品只能选一次。
转化为01背包:
- 通过二进制拆分，我们将多重背包问题成功转化为了一个 01背包问题。新物品的总数是 $\sum O(\log c_i)$ 。
- 接下来，我们应用标准的01背包解法即可。
- 状态定义: $dp[j]$ 表示容量为 $j$ 的背包能获得的最大价值。
- 状态转移: 对于每个拆分出的新物品（体积 $v'$ , 价值 $w'$ ），我们更新 $dp$ 数组： $dp[j] = \max(dp[j], dp[j - v'] + w')$
- 注意：01背包问题的内层循环（背包容量）必须 逆序遍历，以保证每个物品只被选择一次。

代码

c++
java
python

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

using namespace std;

struct Item {
    int v, w;
};

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

        vector<long long> dp(V + 1, 0);
        
        // 01背包
        for (const auto& item : items) {
            for (int j = V; j >= item.v; --j) {
                dp[j] = max(dp[j], dp[j - item.v] + item.w);
            }
        }
        cout << dp[V] << "\n";
    }
    return 0;
}

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

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int N = sc.nextInt();
            int V = sc.nextInt();
            List<Item> items = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                int v = sc.nextInt();
                int w = sc.nextInt();
                int c = sc.nextInt();
                // 二进制拆分
                for (int k = 1; k <= c; k *= 2) {
                    items.add(new Item(v * k, w * k));
                    c -= k;
                }
                if (c > 0) {
                    items.add(new Item(v * c, w * c));
                }
            }

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

            // 01背包
            for (Item item : items) {
                for (int j = V; j >= item.v; j--) {
                    dp[j] = Math.max(dp[j], dp[j - item.v] + item.w);
                }
            }
            System.out.println(dp[V]);
        }
    }
}

T = int(input())
for _ in range(T):
    N, V = map(int, input().split())
    items = []
    for i in range(N):
        v, w, c = map(int, input().split())
        # 二进制拆分
        k = 1
        while k <= c:
            items.append((v * k, w * k))
            c -= k
            k *= 2
        if c > 0:
            items.append((v * c, w * c))

    dp = [0] * (V + 1)
    
    # 01背包
    for v_item, w_item in items:
        for j in range(V, v_item - 1, -1):
            dp[j] = max(dp[j], dp[j - v_item] + w_item)

    print(dp[V])

算法及复杂度

算法：动态规划 (多重背包 + 二进制拆分优化)
时间复杂度： $O(T \cdot V \cdot \sum \log c_i)$ - $T$ 为数据组数， $V$ 为背包容量， $c_i$ 为第 $i$ 种物品的数量。
空间复杂度： $O(V + \sum \log c_i)$ - 主要开销来自 $dp$ 数组和存储拆分后物品的列表。