C++算法一9.第3节 动态规划背包问题.ppt

【参考程序】 #includecstdio #includecstring //初始化memset要用到 using namespace std; int v, u, k; int a[1001], b[1001], c[1001]; int f[101][101]; int main(){ memset(f,127,sizeof(f)); //初始化为一个很大的正整数 f[0][0] = 0; scanf(%d%d%d,v,u,k); for (int i = 1; i = k; i++) scanf(%d%d%d,a[i],b[i],c[i]); for (int i = 1; i = k; i++) for (int j = v; j = 0; j--) for (int l = u; l = 0; l--) { int t1 = j+ a[i],t2 = l + b[i]; if (t1 v) t1 = v; //若氮、氧含量超过需求，可直接用需求量代换， if (t2 u) t2 = u; //不影响最优解 if (f[t1][t2] f[j][l] + c[i]) f[t1][t2] = f[j][l] + c[i]; } printf(%d,f[v][u]); return 0; } 小结 事实上，当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加一维以满足新的限制是一种比较通用的方法。希望你能从本讲中初步体会到这种方法。 六、分组的背包问题 问题 　　　有N件物品和一个容量为V的背包。第i件物品的费用是w[i]，价值是c[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 算法 　　这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有f[k][v]=max{f[k-1][v]，f[k-1][v-w[i]]+c[i]|物品i属于第k组}。 使用一维数组的伪代码如下： for 所有的组k for v=V..0 for 所有的i属于组k 　　　　　　f[v]=max{f[v],f[v-w[i]]+c[i]} 　　注意这里的三层循环的顺序，“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。 另外，显然可以对每组中的物品应用完全背包中“一个简单有效的优化”。 【例6】分组背包 【问题描述】 一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 【输入格式】 第一行：三个整数，V(背包容量，V=200)，N(物品数量，N=30)和T(最大组号，T=10)； 第2..N+1行：每行三个整数Wi,Ci,P，表示每个物品的重量，价值，所属组号。 【输出格式】 仅一行，一个数，表示最大总价值。 【样例输入】group.in 10 6 3 2 1 1 3 3 1 4 8 2 6 9 2 2 8 3 3 9 3 【样例输出】group.out 20 【参考程序】 #includecstdio using namespace std; int v, n, t; int w[31], c[31]; int a[11][32], f[201]; int main(){ scanf(%d%d%d,v,n,t); for (int i = 1; i = n; i++){ 　　 int p; scanf(%d%d%d,w[i],c[i],p); a[p][++a[p][0]] = i; } for (int k = 1; k = t; k++) for (int j