【题目来源】
洛谷：CF106C Buns - 洛谷
【题目描述】
Lavrenty 是一名面包师，他打算制作若干带馅的面包并出售。
Lavrenty 有 \(n\) 克面团，以及 \(m\) 种不同类型的馅料。馅料类型编号为 \(1\) 到 \(m\)。Lavrenty 知道他还剩下第 \(i\) 种馅料 \(a_i\) 克。制作一个第 \(i\) 种馅料的面包需要恰好 \(b_i\) 克该种馅料和 \(c_i\) 克面团。这样的面包可以卖 \(d_i\) 图格里克。
他也可以制作没有馅料的面包。每个这样的面包需要 \(c_0\) 克面团，可以卖 \(d_0\) 图格里克。因此，Lavrenty 可以制作任意数量的带不同馅料或无馅料的面包，直到面团和馅料用完为止。烘焙后剩余的所有材料都会被丢弃。
请你计算 Lavrenty 能获得的最大图格里克数。
【输入】
第一行包含 \(4\) 个整数 \(n\)、\(m\)、\(c_0\) 和 \(d_0\)（\(1 \leq n \leq 1000\)，\(1 \leq m \leq 10\)，\(1 \leq c_0, d_0 \leq 100\)）。接下来的 \(m\) 行，每行包含 \(4\) 个整数。第 \(i\) 行包含 \(a_i\)、\(b_i\)、\(c_i\) 和 \(d_i\)（\(1 \leq a_i, b_i, c_i, d_i \leq 100\)）。
【输出】
输出一个整数，表示 Lavrenty 能获得的最大图格里克数。
【输入样例】
10 2 2 1
7 3 2 100
12 3 1 10
【输出样例】
241
【算法标签】
《洛谷 CF106C Buns》 #背包DP#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 1005; // 数组最大容量
int n, m, c0, d0, p[105], w[105], cnt, ans; // n: 总面团重量，m: 面包种类数，c0/d0: 原始面包的消耗/收益，p: 收益数组，w: 消耗数组，cnt: 物品计数器，ans: 最大收益
int dp[N]; // 动态规划数组int main()
{cin >> n >> m >> c0 >> d0; // 读入总面团重量、面包种类数、原始面包的消耗和收益// 处理每种面包for (int i = 1; i <= m; i++){int a, b, c, d;cin >> a >> b >> c >> d; // 读入：a(可用面团)，b(制作一个需要的基本数量)，c(制作一个的消耗)，d(制作一个的收益)int t = a / b; // 计算可以制作的最大数量// 二进制拆分优化for (int j = 1; j <= t; j *= 2){cnt++;w[cnt] = c * j; // 总消耗p[cnt] = d * j; // 总收益t -= j;}if (t > 0) // 处理剩余部分{cnt++;w[cnt] = c * t;p[cnt] = d * t;}}// 01背包：使用二进制拆分后的物品for (int i = 1; i <= cnt; i++){for (int j = n; j >= w[i]; j--){dp[j] = max(dp[j], dp[j - w[i]] + p[i]);}}// 计算最终答案：考虑制作原始面包for (int j = 0; j <= n; j++){// dp[j]是使用j克面团制作特殊面包的最大收益// 剩余n-j克面团用来制作原始面包ans = max(ans, dp[j] + (n - j) / c0 * d0);}cout << ans << endl; // 输出最大收益return 0;
}
【运行结果】
10 2 2 1
7 3 2 100
12 3 1 10
241