题解 P1064 【金明的预算方案】
heidoudou
2018-08-20 20:46:27
0-1 背包问题的一个变种。 但还是遵循背包问题动态规划的思路。
关键的关键是理解 0-1 背包问题的递归方程：
$dp(n, w) = \max{(dp(n - 1, w), dp(n - 1, w - w_n) + v_n)}$
1. 需要对所有可能的 $1...W$ 计算，而不仅仅是对题目中的约束 $W$ 计算。
2. 一旦确定了 $dp(n, w)$， 那么就可以确定，在 $(n, w)$ 这个子问题中的最优解就是 $dp(n, w)$。
为什么强调第二点，是因为这一题中有一些迷惑人的地方：买了主件之后，到底是买附件呢？还是买附件呢？还是买附件呢？
如何考虑呢？ 如果第 $n$ 个物品是一个主件，需要确定在各种 $w$ 情况下的最优解。 同时 每个 $dp(n, w)$ 有很多种选择
0. 不买， $dp(n - 1, w)$
1. 只买主件 $n$， $dp(n - 1, w - w_n) + v_n$
2. 买一个主件 + 1 个附件， (a, b, c, d....)
3. 买一个主件 + 2 个附件， (a, b) (a, c) (a, d) (b, c) ...
找出来所有这些情况的最大值，也就是最优解。买不买附件由最优解决定。这个最优解告诉我们，在约束为 $w$ 的情况下， 从 $n$ 个物品中选择的最优解就是 $dp(n, w)$，**已经考虑了所有的情况**。
关于这个，想吐槽一下题目出的其实不严谨，或者可以更难一些： 谁规定每个主件如果有附件，则只有两个附件了？ 可以只有一个附件，或者有七八个附件。
对于这种组合问题，有一个很好的解决方法：
1. 开始的时候只有一个主件，一种组合： `{1}`;
2. 有一个附件 2，组合实际上就是， `{1}, {1,2}`
3. 又有一个附件 3， 组合是 `{1}, {1, 2}, {1, 3}, {1, 2, 3}`。 什么规律？ 其实就是在上一个组合集中，每种组合添加一个 3。
4. 同理如果有更多的附件4， 对上一个组合集，每个组合中添加 4，增加4个组合， 构成 8个组合。
当然可以在添加过程中，限制每种组合的数量。
所以我用了 `vector` 变长数组来保存每个组合集。每次遇到新的附件，在原基础上添加就行了。很方便。
剩下的就是背包模板套路了。
最后注意一个优化问题： 背包动规的算法复杂度为 $O(nW)$， 既然题目中所有 $w$ 是 10的倍数，那么所有 $w$ 自除10， 就可以将时间降低一个数量级！！实测很有效： 从 100多ms变成 37ms。
```cpp
using namespace std;
struct object
{
int v;
int vw;
int num;
object(int v, int vw, int n) : v(v), vw(vw), num(n) {}
};
void attach(vector<object> &combo, int v, int vw)
{
int n = combo.size();
for (int i = 0; i < n; ++i)
if (combo[i].num < 2)
combo.push_back(object(combo[i].v + v,
combo[i].vw + vw,
combo[i].num + 1));
}
void update_dp(int dp[], vector<object> &combo, int n)
{
vector<object>::iterator it;
int i, best;
for (i = n; i > 0; --i)
{
best = dp[i];
for (it = combo.begin(); it != combo.end(); ++it)
if (i >= it->v)
best = max(best, dp[i - it->v] + it->vw);
dp[i] = best;
}
}
int main()
{
const int MAX_M = 70; // 最大物品数量
const int MAX_N = 3201; // 最大钱数 / 10
vector<object> objs[MAX_M];
int n, m; // n 钱数上限； m 物品数量
scanf("%d %d", &n, &m);
n /= 10;
int v, w, id;
for (int i = 1; i <= m; ++i)
{
scanf("%d %d %d", &v, &w, &id);
if (!id)
objs[i].push_back(object(v / 10, v / 10 * w, 0));
else
attach(objs[id], v / 10, v / 10 * w);
}
int dp[MAX_N] = { 0 };
for (int i = 1; i <= m; ++i)
if (objs[i].size() > 0)
update_dp(dp, objs[i], n);
printf("%d", dp[n] * 10);
return 0;
}
```