湖南网站建设欧黎明,成都旅游景点排名前十,企业门户网站的主要技术指标,厦门专业制作网站六、分组背包 题记算法题目代码 题记
一个旅行者有一个最多能装V公斤的背包和有N件物品#xff0c;它们的重量分别是W[1]#xff0c;W[2]#xff0c;…,W[n]#xff0c;它们的价值分别为C[1],C[2],…,C[n]。这些物品被划分为若干组#xff0c;每组中的物品互相冲突#… 六、分组背包 题记算法题目代码 题记
一个旅行者有一个最多能装V公斤的背包和有N件物品它们的重量分别是W[1]W[2]…,W[n]它们的价值分别为C[1],C[2],…,C[n]。这些物品被划分为若干组每组中的物品互相冲突最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量且价值总和最大。
算法
这个问题变成了每组物品有若干种策略是选择本组的某一件还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值则有 f [ k ] [ v ] m a x f [ k − 1 ] [ v ] , f [ k − 1 ] [ v − w [ i ] ] c [ i ] 物品 i 属于第 k 组 f[k][v]max{f[k-1][v],f[k-1][v-w[i]]c[i]}物品i属于第k组 f[k][v]maxf[k−1][v],f[k−1][v−w[i]]c[i]物品i属于第k组 使用一维数组的伪代码如下
for 所有的组 kfor vV..0for 所有的 i 属于组 kf[v]max(f[v],f[v-w[i]]c[i])题目
1272【例9.16】分组背包 【题目描述】 一个旅行者有一个最多能装V公斤的背包现在有n件物品它们的重量分别是W1W2…,Wn它们的价值分别为C1,C2,…,Cn。这些物品被划分为若干组每组中的物品互相冲突最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量且价值总和最大。
【输入】 第一行三个整数V(背包容量V≤200)N(物品数量N≤30)和T(最大组号T≤10)
第2…N1行每行三个整数Wi,Ci,P表示每个物品的重量价值所属组号。
【输出】 仅一行一个数表示最大总价值。
【输入样例】
10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3【输出样例】
20代码
#includebits/stdc.h
using namespace std;
int n,v,t;
int w[310],c[310],a[310][310],f[310];
//a[p][0]数组记录每组有多少物品
int main() {cinvnt;for(int i1; in; i) {int p;cinw[i]c[i]p;a[p][a[p][0]]i; }for(int p1; pt; p)for(int jv; j0; j--)for(int i1; ia[p][0]; i)//循环每一组数据中的物品 if(jw[a[p][i]])//保证数组不会越界 f[j]max(f[j],f[j-w[a[p][i]]]c[a[p][i]]);//计算最大价值 coutf[v];//输出在v公斤时的最大价值 return 0;
}
