Description
游戏的主人公有 n 个魔法，每个魔法分为若干个等级，第 i 个魔法有 p[i] 个等级（不包括 0），每个魔法的每个等级都有一个效果值，一个 j 级的 i 种魔法的效果值为 w[i][j]，魔法升一级需要一本相应的魔法书，购买魔法书需要金币，第 i 个魔法的魔法书价格为 c[i]，而小x只有 m 个金币（好孩子不用修改器）。
你的任务就是帮助小x决定如何购买魔法书才能使所有魔法的效果值之和最大，开始时所有魔法为 0 级效果值为 0。
Format
Input
第一行用空格隔开的两个整数 n，m。
以下 n 行，描述 n 个魔法，第 i + 1 行描述第 i 个魔法。格式如下：
c[i] p[i] w[i][1] w[i][2] ... w[i][p[i]]
Output
第一行输出一个整数，即最大效果值。
以后 n 行输出你的方案：
第 i + 1 行有一个整数 v[i]，表示你决定把第 i 个魔法学到 v[i] 级。
如果有多解输出花费金币最少的一组。
如果还多解输出任意一组。
Samples
输入数据 1
3 10
1 3 1 2 2
2 3 2 4 6
3 3 2 1 10
输出数据 1
11
1
0
3
Limitation
对于 100% 的数据，0 ＜ n ≤ 100，0 ＜ m ≤ 500，0 ＜ p[i] ≤ 50，0 ＜ c[i] ≤ 10，保证输入数据和最终结果在 longint 范围内。
浅浅谈一下
-
首先看到题目，第一反应就是
背包! -
仔细看下，没有无限选，就不是
完全背包 -
再仔细看下，每个魔法有\(p_i\)等级，每个等级所花费的钱和收获的钱都不一样
-
诶？怎么有点像
多重背包有点小感觉 -
于是，我们第一个生成的思路就出来了
-
将每个魔法分成\(p_i\)个物品，再做多重背包
-
诶？等下，有点问题
-
一个魔法可以选择多个等级吗？
-
并不能！说明了什么？
-
每个魔法分成的\(p_i\)个物品互相排斥！
-
对于多组物品，每组物品互相排斥，只能挑一个，怎么做呢？
-
分组背包应运而生！
分组背包
- 解决问题
有一个体积为\(v\)的背包，\(n\)个物体，重量分别为\(w_1……w_n\),价值分别为\(c_1……c_n\),被分为若干组，每组中的物品互相冲突，最多选一件，求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大
- 问题分析
-
首先，我们也是枚举物品，枚举价钱，定个一维数组，主要是循环顺序
-
同一组的物品互相排斥，互相不能选择，我们\(dp\)是怎么转移的？
-
是从前面的状态转移的！
-
既然在前面的状态不能出现这个组成员更新过的值
-
我们就把枚举价值的放外层（倒着枚举），枚举这组成员放里层，让这一组的成员从数组最后一直推到数组前就行了
- 结合代码更好食用
\(\mathcal{Code}\)
cin>>v>>n>>t;
for(int i=1;i<=n;i++){
int pp;cin>>w[i]>>c[i]>>pp;
p[pp][++p[pp][0]]=i;
}
for(int i=1;i<=t;i++)
for(int j=v;j>=0;j--)
for(int k=1;k<=p[i][0];k++)
if(j>=w[p[i][k]])
f[j]=max(f[j],f[j-w[p[i][k]]]+c[p[i][k]]);
cout<<f[v];
注:\(p_{i\ 0}\)存的是这个组成员的数量以前的代码比较丑，见谅
回到本题
-
于是我们就可以把分组背包代码放上去，但是，又有个问题
-
还让我们记录路径！
** -
在开始打代码的之前，我们要想好我们要记录什么
-
按照以前的经验，肯定是用个二维数组，记录
-
但是这道题不同，但让我们记录有谁不能选，输出0
** -
于是我们就要记录他在哪个组
-
又由于这道题他让我们输出等级，我们也要记录他的等级
-
于是我们就可以用个结构体装
struct node{int dj, zb, v;}
-
如果以前的状态比现在这个优，我们首先要把以前的状态全部继承到现在的这个状态，然后在更新即可啊
-
动态规划部分代码
\(\mathcal{Code}\)
for (int i = 1; i <= cnt; i++)
for (int j = m; j >= 0; j--)
for (int k = 1; k <= p[i]; k++)
if(j >= w[i][k].v && dp[j] < dp[j - w[i][k].v] + v[i][k].v) {
dp[j] = dp[j - w[i][k].v] + v[i][k].v;
for (int q = 1; q <= ans[j - w[i][k].v][0].v; q++) ans[j][q] = ans[j - w[i][k].v][q];
ans[j][0].v = ans[j - w[i][k].v][0].v + 1;
ans[j][ans[j][0].v].dj = w[i][k].dj, ans[j][ans[j][0].v].zb = i;
}
- 由于题目要求我们输出花费金币最少的一组，我们还要做个比较
int maxx = 0, max_id = 0;
for (int i = 0; i <= m; i++)
if(maxx < dp[i])
maxx = dp[i], max_id = i;
- 最后用个桶装住，更好地帮助我们输出哪里是\(0\)
完整代码
\(\mathcal{Code}\)高清无码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 3e3 + 7;
struct node{int dj, zb, v;}w[MAXN][MAXN], v[MAXN][MAXN], ans[MAXN][MAXN];
int n, m;
int c[MAXN], p[MAXN], cnt, dp[MAXN], zans[MAXN];
signed main() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", c + i, p + i);
cnt++;
for (int j = 1; j <= p[i]; j++) {
int x; scanf("%lld", &x);
w[cnt][j].v = c[i] * j, v[cnt][j].v = x;
w[cnt][j].dj = j, v[cnt][j].dj = j;
w[cnt][j].zb = i, v[cnt][j].zb = i;
}
}
for (int i = 1; i <= cnt; i++)
for (int j = m; j >= 0; j--)
for (int k = 1; k <= p[i]; k++)
if(j >= w[i][k].v && dp[j] < dp[j - w[i][k].v] + v[i][k].v) {
dp[j] = dp[j - w[i][k].v] + v[i][k].v;
for (int q = 1; q <= ans[j - w[i][k].v][0].v; q++) ans[j][q] = ans[j - w[i][k].v][q];
ans[j][0].v = ans[j - w[i][k].v][0].v + 1;
ans[j][ans[j][0].v].dj = w[i][k].dj, ans[j][ans[j][0].v].zb = i;
}
int maxx = 0, max_id = 0;
for (int i = 0; i <= m; i++)
if(maxx < dp[i])
maxx = dp[i], max_id = i;
printf("%lld\n", dp[max_id]);
for (int i = 1; i <= ans[max_id][0].v; i++)
zans[ans[max_id][i].zb] = ans[max_id][i].dj;
for (int i = 1; i <= n; i++)
printf("%lld\n", zans[i]);
return 0;
}
完结撒花
