P2639 [USACO09OCT] Bessie‘s Weight Problem G

记录107

#include<bits/stdc++.h> using namespace std; bool dp[45010]; int main(){ int n,h,s;//几捆草，最大草量，每捆重量 cin>>h>>n;//输入 dp[0]=1;//初始dp起点 for(int i=1;i<=n;i++){//遍历每捆草 cin>>s;//输入斤数 for(int j=h;j>=s;j--){//斤数是背包 if(j-s>=0&&dp[j-s]) dp[j]=1;//斤数是否合法 } } for(int j=h;j>0;j--){//从最大斤数开始向后找 if(dp[j]){//找到满足的了 cout<<j;//输出 break;//跳出循环 } } return 0;//结束程序 }

题目传送门https://www.luogu.com.cn/problem/P2639

突破口

Bessie 像她的诸多姊妹一样，因为从 Farmer John 的草地吃了太多美味的草而长出了太多的赘肉。所以 FJ 将她置于一个及其严格的节食计划之中。她每天不能吃多过 H(5≤H≤45,000) 公斤的干草。 Bessie 只能吃一整捆干草；当她开始吃一捆干草的之后就再也停不下来了。她有一个完整的N(1≤N≤500) 捆可以给她当作晚餐的干草的清单。她自然想要尽量吃到更多的干草。很自然地，每捆干草只能被吃一次（即使在列表中相同的重量可能出现 2 次，但是这表示的是两捆干草，其中每捆干草最多只能被吃掉一次）。 给定一个列表表示每捆干草的重量 Si​(1≤Si​≤H) , 求 Bessie 不超过节食的限制的前提下可以吃掉多少干草（注意一旦她开始吃一捆干草就会把那一捆干草全部吃完）。

🔍 一、题目核心理解

🎯 问题描述

• Bessie 每天最多吃H 公斤干草（不能超过）
• 有N 捆干草，每捆重量为S_i（1 ≤ S_i ≤ H）
• 每捆只能吃一次（即使重量相同，也是不同捆）
• 一旦开始吃一捆，就必须吃完
• 目标：在不超过 H 的前提下，吃尽可能多的干草（总重量最大）

✅ 这是一个经典的0-1 背包问题：

• 背包容量 = H
• 每个物品重量 = S_i，价值 = S_i（因为目标是最大化总重量）
• 求不超过容量的最大总价值 → 即最大总重量

但注意：我们不需要记录“价值”，只需要知道某个总重量是否可达→ 可用布尔型 DP（可行性 DP）

📌 输入样例解析

56 4 15 19 20 21

• H = 56, N = 4
• 干草重量：15, 19, 20, 21
• 最优组合：15 + 20 + 21 = 56 → 正好达到上限 → 输出 56 ✅

🧠 二、解题思路：0-1 背包（可行性 + 贪心找最大）

方法选择

• 定义dp[w] = true表示总重量 w 是可以达到的
• 初始化：dp[0] = true（不吃任何草，重量为 0）
• 对每捆草s，做 0-1 背包更新（倒序）
• 最终：从w = H往下找，第一个dp[w] == true就是答案

#include<bits/stdc++.h> using namespace std; bool dp[45010]; // dp[w]：是否能恰好吃到 w 公斤干草

• 数组大小45010：因为H ≤ 45000，安全起见开到 45010

int main(){ int n, h, s; // n: 干草捆数, h: 最大允许重量, s: 当前干草重量 cin >> h >> n; // 读入 H 和 N

dp[0] = 1; // 初始状态：不吃任何草，总重量为 0（可达）

• 全局数组默认初始化为false，所以只需设dp[0]=true

for(int i = 1; i <= n; i++){ // 遍历每一捆干草 cin >> s; // 读入当前干草的重量

for(int j = h; j >= s; j--){ // 倒序遍历可能的总重量 if(j - s >= 0 && dp[j - s]) dp[j] = 1; // 如果 j-s 可达，则 j 也可达 } }

🔄 背包更新详解：

• 外层：处理第i捆草
• 内层：从h到s倒序遍历总重量j
• 如果dp[j - s] == true，说明加上当前这捆草后可以达到j
• 标记dp[j] = true

✅ 这是标准的0-1 背包可行性更新

• 倒序防止同一捆草被重复使用

for(int j = h; j > 0; j--){ // 从最大可能重量往下找 if(dp[j]){ // 找到第一个可达的重量 cout << j; // 输出 break; // 立即退出 } }

• 因为要最大重量，所以从H开始往下找
• 第一个true就是答案

⚠️ 注意：题目保证至少可以吃 0 公斤，但输出要求是“最多吃多少”，而j > 0，但如果所有草都吃不下（比如最小草 > H），会输出什么？

• 实际上，dp[0]=true，但循环j>0，所以如果没有任何正重量可达，不会输出任何东西？

但题目说明：“Bessie 只能吃一整捆干草”，且S_i ≥ 1，H ≥ 5，数据保证有解（至少可以吃 0，但通常有正解）。而且样例和实际比赛中，总会有一个正解或 0。

不过严格来说，应考虑j >= 0，但题目隐含至少可以不吃（0），而输出要求是“最多吃多少”，如果实在吃不下任何一捆，答案就是 0。

但本题输入约束S_i ≥ 1,H ≥ 5，且N ≥ 1，很可能总有正解。而且样例输出 56 > 0。

✅ 在本题上下文中，这样写是安全的。

return 0; }

⚠️ 关键细节说明

总结：问题与解法对应