P1776 宝物筛选

May 5, 2026 · 6 分钟阅读 · 背包问题动态规划 ·

文章目录

题目信息

字段	内容
题号	P1776
难度	绿题（普及+）
知识点	多重背包、二进制优化、动态规划

题目描述

终于，破解了千年的难题。小 F 找到了王室的宝库，里面堆满了无数价值连城的宝物。

但是这里的宝物实在是太多了，小 F 的采集车似乎装不下那么多宝物。看来小 F 只能含泪舍弃其中的一部分宝物了。

小 F 对宝库里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：

小 F 有一个最大载重为 W 的采集车，宝库里总共有 n 种宝物，每种宝物的价值为 v、重量为 w、每种宝物有 m 件。小 F 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

输入格式

第一行两个整数 n 和 W，分别表示宝物种数和采集车的最大载重。

接下来 n 行，每行三个整数 v、w、m，分别表示该种宝物的价值、重量和数量。

输出格式

输出一个整数，表示在采集车不超载的情况下收集的宝物的最大价值。

样例

输入

输出

解题思路

核心思想

本题是经典的多重背包（Multiple Knapsack） 问题。每种宝物有 m 件，需要选择若干件装入容量为 W 的背包，使总价值最大。

朴素的解法是把每件物品展开成 m 个单独的物品，变成 m × n 个 0/1 背包物品，但这样复杂度太高。

二进制优化是解决多重背包的标准技巧：将数量 m 拆分成若干个「2 的幂」之和，从而把多重背包转化为若干个 0/1 背包物品。

举个例子，假设某种宝物有 25 件：

拆成 1、2、4、8、10（最后的 10 是余数）
这 5 个新物品，每个可以选或不选，组合起来恰好可以表示 0~25 件的所有选择

具体拆法：对于数量 m，从 2^0、2^1、2^2… 依次贪心取，直到不够取为止，剩余部分作为一个单独的物品。

算法步骤

预处理：计算 2^0 ~ 2^20 存入数组 pow2[i]
二进制拆分：遍历每种宝物，将其数量 m 按上述方式拆成若干新物品（价值、重量同时乘以拆分系数）
0/1 背包 DP：对拆分后的每个新物品做标准 0/1 背包 DP（逆序遍历容量）
答案：dp[W] 即为最大价值

完整代码

C++

#include <cstdio>
#include <cstring>

const int kMaxN = 2000;
const int kMaxW = 50000;

int n;
int capacity;
int item_count = 0;
int weight[kMaxN];
int value[kMaxN];
int dp[kMaxW];

int pow2[21];

void Init() {
    pow2[0] = 1;
    for (int i = 1; i <= 20; ++i) {
        pow2[i] = pow2[i - 1] * 2;
    }
}

void InputData() {
    scanf("%d%d", &n, &capacity);
    for (int i = 1; i <= n; ++i) {
        int v, w, m;
        scanf("%d%d%d", &v, &w, &m);
        int now = 0;
        // 贪心地拆分成 2 的幂
        while (m >= pow2[now]) {
            ++item_count;
            weight[item_count] = pow2[now] * w;
            value[item_count] = pow2[now] * v;
            m -= pow2[now];
            ++now;
        }
        // 处理剩余数量
        if (m > 0) {
            ++item_count;
            weight[item_count] = m * w;
            value[item_count] = m * v;
        }
    }
}

void Solve() {
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= item_count; ++i) {
        for (int j = capacity; j >= weight[i]; --j) {
            dp[j] = dp[j] > dp[j - weight[i]] + value[i] ? dp[j] : dp[j - weight[i]] + value[i];
        }
    }
}

void Output() {
    printf("%d\n", dp[capacity]);
}

int main() {
    Init();
    InputData();
    Solve();
    Output();
    return 0;
}

Python

import sys

def init_pow2():
    pow2 = [1]
    for _ in range(20):
        pow2.append(pow2[-1] * 2)
    return pow2


def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    capacity = int(next(it))

    pow2 = init_pow2()
    items: list[tuple[int, int]] = []

    for _ in range(n):
        v = int(next(it))
        w = int(next(it))
        m = int(next(it))
        now = 0
        while m >= pow2[now]:
            items.append((pow2[now] * w, pow2[now] * v))
            m -= pow2[now]
            now += 1
        if m > 0:
            items.append((m * w, m * v))

    dp = [0] * (capacity + 1)
    for wt, val in items:
        for j in range(capacity, wt - 1, -1):
            if dp[j - wt] + val > dp[j]:
                dp[j] = dp[j - wt] + val

    print(dp[capacity])


if __name__ == "__main__":
    solve()

Java

import java.io.*;
import java.util.*;

public class Main {

    private static final int MAX_ITEMS = 2000;
    private static final int MAX_W = 50000;

    private static int[] pow2 = new int[21];
    private static int[] weight = new int[MAX_ITEMS];
    private static int[] value = new int[MAX_ITEMS];
    private static int[] dp = new int[MAX_W];

    private static void initPow2() {
        pow2[0] = 1;
        for (int i = 1; i <= 20; ++i) {
            pow2[i] = pow2[i - 1] * 2;
        }
    }

    private static int readInt() throws IOException {
        int c;
        do {
            c = System.in.read();
            if (c == -1) return -1;
        } while (c <= ' ');
        int sign = 1;
        if (c == '-') {
            sign = -1;
            c = System.in.read();
        }
        int x = 0;
        while (c > ' ') {
            x = x * 10 + (c - '0');
            c = System.in.read();
        }
        return x * sign;
    }

    public static void main(String[] args) throws Exception {
        initPow2();
        int n = readInt();
        int capacity = readInt();

        int itemCount = 0;
        for (int i = 0; i < n; ++i) {
            int v = readInt();
            int w = readInt();
            int m = readInt();
            int now = 0;
            while (m >= pow2[now]) {
                weight[itemCount] = pow2[now] * w;
                value[itemCount] = pow2[now] * v;
                m -= pow2[now];
                ++now;
                ++itemCount;
            }
            if (m > 0) {
                weight[itemCount] = m * w;
                value[itemCount] = m * v;
                ++itemCount;
            }
        }

        Arrays.fill(dp, 0, capacity + 1, 0);
        for (int i = 0; i < itemCount; ++i) {
            for (int j = capacity; j >= weight[i]; --j) {
                int candidate = dp[j - weight[i]] + value[i];
                if (candidate > dp[j]) {
                    dp[j] = candidate;
                }
            }
        }

        System.out.print(dp[capacity]);
    }
}

Go

package main

import (
    "bufio"
    "fmt"
    "os"
)

func initPow2() []int {
    pow2 := make([]int, 21)
    pow2[0] = 1
    for i := 1; i <= 20; i++ {
        pow2[i] = pow2[i-1] * 2
    }
    return pow2
}

// readInt 从标准输入读取一个整数
func readInt(scanner *bufio.Scanner) int {
    if !scanner.Scan() {
        return 0
    }
    var x int
    fmt.Sscanf(scanner.Text(), "%d", &x)
    return x
}

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanWords)

    pow2 := initPow2()

    n := readInt(scanner)
    capacity := readInt(scanner)

    type item struct {
        weight int
        value  int
    }
    var items []item

    for i := 0; i < n; i++ {
        v := readInt(scanner)
        w := readInt(scanner)
        m := readInt(scanner)
        now := 0
        for m >= pow2[now] {
            items = append(items, item{
                weight: pow2[now] * w,
                value:  pow2[now] * v,
            })
            m -= pow2[now]
            now++
        }
        if m > 0 {
            items = append(items, item{
                weight: m * w,
                value:  m * v,
            })
        }
    }

    dp := make([]int, capacity+1)
    for _, it := range items {
        for j := capacity; j >= it.weight; j-- {
            candidate := dp[j-it.weight] + it.value
            if candidate > dp[j] {
                dp[j] = candidate
            }
        }
    }

    fmt.Println(dp[capacity])
}

JavaScript

'use strict';

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const lines = [];
rl.on('line', (line) => {
    lines.push(line.trim());
}).on('close', () => {
    solve(lines);
});

function solve(lines) {
    if (lines.length === 0) return;
    const first = lines[0].split(/\s+/).map(Number);
    const n = first[0];
    const capacity = first[1];

    const pow2 = [1];
    for (let i = 1; i <= 20; i++) {
        pow2.push(pow2[i - 1] * 2);
    }

    const items = [];
    let idx = 1;
    for (let i = 0; i < n; i++) {
        const [v, w, m] = lines[idx].split(/\s+/).map(Number);
        idx++;
        let num = m;
        let now = 0;
        while (num >= pow2[now]) {
            items.push([pow2[now] * w, pow2[now] * v]);
            num -= pow2[now];
            now++;
        }
        if (num > 0) {
            items.push([num * w, num * v]);
        }
    }

    const dp = new Array(capacity + 1).fill(0);
    for (const [wt, val] of items) {
        for (let j = capacity; j >= wt; j--) {
            const candidate = dp[j - wt] + val;
            if (candidate > dp[j]) {
                dp[j] = candidate;
            }
        }
    }

    process.stdout.write(String(dp[capacity]));
}

关键代码讲解

1. 二进制拆分

int now = 0;
while (m >= pow2[now]) {
    ++item_count;
    weight[item_count] = pow2[now] * w;   // 重量扩大
    value[item_count] = pow2[now] * v;     // 价值扩大
    m -= pow2[now];
    ++now;
}
if (m > 0) {
    ++item_count;
    weight[item_count] = m * w;
    value[item_count] = m * v;
}

核心思想：数量为 m 的物品，拆成 1、2、4、8、...、2^k 以及一个余数 r。通过这 k+1 个物品的 0/1 选择，可以组合出 0~m 的任意数量。这是因为二进制表示的任意性保证了这一点。

2. 0/1 背包 DP

for (int i = 1; i <= item_count; ++i) {
    for (int j = capacity; j >= weight[i]; --j) {
        dp[j] = dp[j] > dp[j - weight[i]] + value[i]
                ? dp[j]
                : dp[j - weight[i]] + value[i];
    }
}

必须逆序遍历容量 j = capacity ... weight[i]：如果正序遍历，同一个物品会被多次选择，变成完全背包。逆序保证了每个新物品只被使用一次，即 0/1 背包的特性。

复杂度分析

方法	时间复杂度	空间复杂度
二进制优化多重背包	O(n × log m × W)	O(W)

n：宝物种数
m：每种宝物的最大数量（拆分后约 log₂m 个物品）
W：背包容量（dp 数组大小）

空间优化：本题已使用一维 dp 数组，达到最优空间复杂度 O(W)。

易错点

二进制拆分后漏掉余数：当数量 m 不能完整拆成 2 的幂之和时，剩余的不足部分（如样例中 25 → 1+2+4+8+10）必须单独作为一个物品，否则会漏掉某些取法。
Java 禁止使用 Scanner：在洛谷等 OJ 平台，使用 Scanner 会因大量 I/O 导致 MLE（内存超限）。必须使用 BufferedInputStream + 手动字节解析或 BufferedReader。
dp 逆序更新：0/1 背包必须从大到小遍历容量，确保物品不被重复放入。