[USACO09OCT] Bessie's Weight Problem G

GitHub跳转原题关系图返回列表

把每捆干草的重量同时看成重量和价值，用一维 0/1 背包求不超过 H 的最大总重量。

OJ: luogu

题目 ID: P2639

难度:普及-

标签:动态规划01背包背包

创建: 2026-06-19 15:24

更新: 2026-10-07 10:45

后置题目
luogu P1734最大约数和B 主解把 A 教的「一维 dp 内层容量倒序枚举、每件物品最多选一次」原样搬入自己的 main.cpp（for(j=s;j>=i;--j) dp[j]=max(dp[j],dp[j-i]+val[i])），只是先补上真约数和预处理这一步；A 的 dp[j] 状态含义从「容量 j 内最大重量」换成「总和 j 内最大约数和」，模板完全一致。luogu P1507NASA的食物计划A 讲透的「每件物品只能选一次 ⇒ 容量必须倒序枚举」正是 B 的二维费用 0/1 背包实际使用的步骤：B 把 A 的一维容量 dp[j] 扩成体积、质量两维 dp[j][k]，并在两维上继续倒序枚举（main.cpp:22-23 的 for(j=H;j>=h;--j) / for(l=T;l>=t;--l)），从而保证每件食品最多选一次；A 是纯 0/1 背包基础题，B 叠加的是体积+质量双重限制这一台阶，难度 普及- → 普及/提高-，方向正确。

目录

  1. 题意
  2. 思路
    1. 代码
    2. 复杂度
    3. 总结
    4. 一图流解析

    题意

    给出 N 捆干草，每捆都有一个重量 S[i]。

    • 每捆干草最多只能吃一次
    • 总重量不能超过上限 H

    要求在不超过 H 的前提下，让 Bessie 吃到的总重量尽量大。

    这张表把题目直接翻译成了背包模型：

    原题对象 背包含义
    一捆干草 一个只能选一次的物品
    干草重量 S[i] 物品重量
    干草重量 S[i] 物品价值
    上限 H 背包容量

    从表里可以看到，本题没有额外花样，本质上就是“总重量不超过 H 时，最多能装多少重量”。

    思路

    先看最直接的暴力：

    cpp
    #include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解，使用 01 序列枚举每捆干草吃或不吃。

const int MAXN = 505;

int h, n;
int weight[MAXN];
int choose_hay[MAXN]; // choose_hay[i] = 0/1，表示第 i 捆干草不吃/吃
int answer;

int calc_weight() {
    int total_weight = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_hay[i] == 1) total_weight += weight[i];
    }
    return total_weight;
}

bool check() {
    return calc_weight() <= h;
}

void dfs_choose(int dep) {
    if (dep == n + 1) {
        if (check()) {
            int value = calc_weight();
            if (answer < value) answer = value;
        }
        return;
    }

    // 第 dep 捆干草的 01 选择：0 不吃，1 吃。
    for (int i = 0; i <= 1; i++) {
        choose_hay[dep] = i;
        dfs_choose(dep + 1);
    }
}

void read_input() {
    cin >> h >> n;
    for (int i = 1; i <= n; i++) {
        cin >> weight[i];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    dfs_choose(1);
    cout << answer << '\n';

    return 0;
}

    brute.cpp 把每捆干草看成一个 01 选择：choose_hay[i] = 0/1 表示不吃或吃。递归先生成完整选择，叶子节点再检查总重量是否超过 H。

    这个做法显然正确，但复杂度是 O(2N)O(2^N)，只能做小数据验证。

    关键观察是：每捆干草的重量既限制了“能不能选”，又正好等于“选了之后获得多少收益”。

    所以设：

    • dp[j] 表示总重量不超过 j 时，最多能吃到多少干草

    这张表说明状态定义：

    状态 含义
    dp[j] 总重量不超过 j 时，最多能吃到多少干草

    处理一捆重量为 w 的干草时：

    • 不吃它：dp[j] 保持原值
    • 吃它：从 dp[j - w] 转移过来，再加上 w

    于是转移就是：

    • dp[j] = max(dp[j], dp[j - w] + w)

    因为每捆干草只能吃一次，所以容量必须倒序枚举。

    最后输出 dp[H] 即可。

    DP 公式

    设 dpjdp_j 表示总重量不超过 jj 时最多能吃到多少干草。处理重量为 wiw_i 的干草时：

    dpj=max⁡(dpj, dpj−wi+wi) dp_j=\max(dp_j,\ dp_{j-w_i}+w_i)

    其中 j⩾wij\geqslant w_i，并且容量倒序枚举。最终答案为：

    dpH dp_H

    公式解释：每捆干草的重量既是容量消耗，也是收益。状态记录容量内能吃到的最大重量，因此转移形式和 0/1 装箱完全一样。

    代码

    cpp
    #include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;
const int MAXH = 45005;

int h, n;
int weight[MAXN];
int dp[MAXH]; // dp[j] 表示总重量不超过 j 时，最多能吃到多少干草

void read_input() {
    cin >> h >> n;
    for (int i = 1; i <= n; i++) {
        cin >> weight[i];
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        // 每捆干草只能吃一次，所以容量必须倒序枚举。
        for (int j = h; j >= weight[i]; j--) {
            dp[j] = max(dp[j], dp[j - weight[i]] + weight[i]);
        }
    }

    cout << dp[h] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

    复杂度

    • 时间复杂度：O(NH)O(NH)
    • 空间复杂度：O(H)O(H)

    总结

    这题和普通 0/1 背包几乎完全一样，只是物品价值刚好等于物品重量。

    以后看到“每个对象最多选一次，不能超过一个总上限，并且目标是尽量填满”这类条件时，就可以优先往一维 0/1 背包上想。

    一图流解析

    这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

    一图流解析