Merlin's Blog
Just record something
Toggle navigation
Merlin's Blog
Home
Scratch基础教程
About Me
Archives
Tags
分组背包
分组背包
2019-02-10 13:54:18
140
0
0
merlin
分组背包
##**问题** 有$N$件物品和一个容量为$V$的背包。第$i$件物品的费用是$C_i$，价值是$W_i$。这 些物品被划分为$K$组，每组中的物品互相冲突，最多选一件。求解将哪些物品 装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 ##**算法** 这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设$F[k,v]$表示前$k$组物品花费费用$v$能取得的最大权值，则有： $F[k, v] = max(F[k − 1, v], F[k − 1, v − Ci ] + Wi | item i ∈ group k)$ **<font color=red>也就是说第k组的物品$i$不放，就从前面$k-1$组同等大小的背包$v$中转移；如果放，同理，从前面$k-1$组的$v-c_i$背包加上当前物品的价值。</font>** 使用一维数组的伪代码如下： ``` for k = 1 to K //按组扫描 for v = V to 0 //枚举状态：背包空间。倒推确保放一次。同01背包 for item i in group k //扫描第k组的物品 F[v] = max{F[v], F[v − Ci ] + Wi} //状态转移 ``` 这里三层循环的顺序保证了每一组内的物品最多只有一个会被添加到背包中。 ##**实战练习** OJ:1887 这次没使用vector，用数组模拟邻接表，因为数据足够小 ``` #include <bits/stdc++.h> using namespace std; int dp[205],w[40],c[40],V,n,t,p,a[20][40]; int main() { cin >> V >> n >> t; for(int i = 1; i <= n; ++i){ cin >> w[i] >> c[i] >> p; a[p][0]++; //p组计数 a[p][a[p][0]] = i; //记录物品下标 } for(int k = 1; k <= t; ++k) //按组号枚举 for(int v=V; v>=0; --v) //枚举状态：背包空间。倒推确保只装1次，同01背包 for(int i=1; i <= a[k][0]; ++i){ //扫描物品 int num = a[k][i]; //取出物品下标 if (v>=w[num]) //能装 dp[v]=max(dp[v],dp[v-w[num]]+c[num]); //从上一阶段转移过来 } cout << dp[V] << endl; return 0; } ```
Pre:
【Scratch】第三课：大鱼吃小鱼(克隆版)（2课时）
Next:
表达式转换及计算
0
likes
140
Weibo
Wechat
Tencent Weibo
QQ Zone
RenRen
Table of content
merlin
