9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

背包问题2012



背包问题 之 01背包问题

? 我们来看一下问题: ? 一个旅行者有一个最多能用M公斤的背包,现在有N件物 品, 它们的重量分别是W1,W2,...,Wn, 它们的价值分别为P1,P2,...,Pn. 若每种物品只有一件求旅行者能获得最大总价值。 输入格式: M,N W1,P1 W2,P2 ...... 输出格式: X

? 因为背包

最大容量M未知。所以,我们的程序要 从1到M一个一个的试。比如,开始任选N件物品 的一个。看对应M的背包,能不能放进去,如果 能放进去,并且还有多的空间,则,多出来的空 间里能放N-1物品中的最大价值。怎么能保证总选 择是最大价值呢?看下表。 测试数据: 10,3 3,4 4,5 5,6

? 考虑用动态规划的方法来解决,这里的: 阶段是:在前n件物品中,选取若干件物品放入背包中; 状态是:在前n件物品中,选取若干件物品放入所剩空间 为w的背包中的所能获得的最大价值; 决策是:第n件物品放或者不放; 由此可以写出动态转移方程: 我们用f[i,j]表示在前 i 件物品中选择若干件放在所剩空间 为 j 的背包里所能获得的最大价值 f[i,j]=max{f[i-1,j-wi]+pi (j>=wi), f[i-1,j]}

这样,我们可以自底向上地得出在前m件物品中取出若干 件放进背包能获得的最大价值,也就是f[m,w]

? 算法设计如下: ? procedure make; begin for i:=0 to m do f[0,i]:=0; for i:=1 to n do for j:=0 to m do begin f[i,j]:=f[i-1,j]; if (j>=w[i]) and (f[i-1,j-w[i]]+v[i]>f[i,j]) then f[i,j]:=f[i-1,j-w[i]]+v[i]; end; writeln(f[n,m]); end;

优化方法
? 时间上无法优化,空间上可以 ? 一种方法:滚动数组 ? 动规方程中,i只和i-1有关系,故方程可以 用f1,f2来代替i-1,i.

? procedure make; begin fillchar(f,sizeof(f),0); ? for i:=1 to n do ? begin for j:=0 to m do begin f[2,j]:=f[1,j]; if (j>=w[i]) and (f[1,j-w[i]]+v[i]>f[2,j]) then f[2,j]:=f[1,j-w[i]]+v[i]; end; f[1]:=f[2]; ? end; ? writeln(f[1,m]); end;

? 优化空间复杂度 ? 以上方法的时间和空间复杂度均为O(VN),其中时间复杂 度应该已经不能再优化了,但空间复杂度却可以优化到O。 ? 先考虑上面讲的基本思路如何实现,肯定是有一个主循环 i=1..N,每次算出来二维数组f[i][0..V]的所有值。那么,如 果只用一个数组f[0..V],能不能保证第i次循环结束后f[v]中 表示的就是我们定义的状态f[i][v]呢?f[i][v]是由f[i-1][v]和 f[i-1][v-c[i]]两个子问题递推而来,能否保证在推f[i][v]时 (也即在第i次主循环中推f[v]时)能够得到f[i-1][v]和f[i1][v-c[i]]的值呢?事实上,这要求在每次主循环中我们以 v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的 是状态f[i-1][v-c[i]]的值。伪代码如下:
? for i=1..N ? for v=V..0 ? f[v]=max{f[v],f[v-c[i]]+w[i]};

? 详细讲解过程

1、采药
?

? ? ?

【问题描述】 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近 最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一 个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株 都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你 可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最 大。” 如果你是辰辰,你能完成这个任务吗? 【输入文件】 输入文件medic.in的第一行有两个整数T(1 <= T <= 1000)和M(1 <= M <= 100), 用一个空格隔开,T代表总共能够用来采药的时间,M代表山洞里的草药的数目。接下 来的M行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药 的时间和这株草药的价值。 【输出文件】 输出文件medic.out包括一行,这一行只包含一个整数,表示在规定的时间内,可以 采到的草药的最大总价值。

? ? ?

? ?

? ? ? ? ? ? ? ? ? ?

【样例输入】 70 3 71 100 69 1 12 【样例输出】 3 【数据规模】 对于30%的数据,M <= 10; 对于全部的数据,M <= 100。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

程序如下: var t,n,i,j,max:integer; f:array[1..2,0..1000] of integer; w,c:array[1..100] of integer; begin assign(input,'medic.in'); reset(input); assign(output,'medic.out');rewrite(output); readln(t,n); for i:=1 to n do readln(w[i],c[i]); fillchar(f,sizeof(f),0); for i:=1 to n do begin for j:=0 to t do begin f[2,j]:=f[1,j]; if (j>=w[i]) and (f[1,j-w[i]]+c[i]>f[2,j]) then f[2,j]:=f[1,j-w[i]]+c[i]; end; f[1]:=f[2]; end; writeln(f[1,t]); close(input); close(output);

采药 (medic.pas/c/cpp)
? 【问题描述】 ? 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。 为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给 他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说: “孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间, 每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可 以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草 药的总价值最大。” 如果你是辰辰,你能完成这个任务吗? ? 【输入文件】 ? 输入文件medic.in的第一行有两个整数T(1 <= T <= 1000)和M(1 <= M <= 100),用一个空格隔开,T代表总共能够用来采药的时间, M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之 间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药 的价值。

【输出文件】 输出文件medic.out包括一行,这一行只包含一个整数,表示在规定的 时间内,可以采到的草药的最大总价值。 【样例输入】 70 3 71 100 69 1 1 2 【样例输出】 3 【数据规模】 对于30%的数据,M <= 10; 对于全部的数据,M <= 100。

主要程序如下: readln(t,n); for i:=1 to n do readln(w[i],c[i]); fillchar(f,sizeof(f),0); for i:=1 to n do for j:=t downto w[i] do if f[j]<f[j-w[i]]+c[i] then f[j]:=f[j-w[i]]+c[i]; writeln(f[t]);

注意边界问题

? 初始化的细节问题 ? 我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问 法。有的题目要求“恰好装满背包”时的最优解,有的题目则并没有 要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的 时候有所不同。 ? 如果是第一种问法,要求恰好装满背包,那么在初始化时除了f[0]为0 其它f[1..V]均设为-∞,这样就可以保证最终得到的f[N]是一种恰好装 满背包的最优解。 ? 如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时 应该将f[0..V]全部设为0。 ? 为什么呢?可以这样理解:初始化的f数组事实上就是在没有任何物 品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只 有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量 的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞ 了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解 “什么都不装”,这个解的价值为0,所以初始时状态的值也就全部 为0了。 ? 这个小技巧完全可以推广到其它类型的背包问题,后面也就不再对进 行状态转移之前的初始化进行讲解。

初始不同,写的方式也应不同

? readln(t,m); ? for i:=1 to m do readln(a[i],v[i]); ? for i:=0 to t do c[i]:=-maxint+1; ? c[0]:=0; ? for j:=1 to m do ? for i:=t downto a[j] do ? if (c[i-a[j]]+v[j])>c[i] then c[i]:=c[i-a[j]]+v[j]; ? sum:=0; ? for i:=t downto 0 do ? if sum<c[i] then sum:=c[i]; ? writeln(sum);

背包之 完全背包问题

完全背包问题
? 题目 ? 有N种物品和一个容量为V的背包,每种物 品都有无限件可用。第i种物品的费用是c[i], 价值是w[i]。求解将哪些物品装入背包可使 这些物品的费用总和不超过背包容量,且 价值总和最大。

基本思路
? 这个问题非常类似于01背包问题,所不同的是每 种物品有无限件。也就是从每种物品的角度考虑, 与它相关的策略已并非取或不取两种,而是有取0 件、取1件、取2件……等很多种。如果仍然按照 解01背包时的思路,令f[i][v]表示前i种物品恰放入 一个容量为v的背包的最大权值。仍然可以按照每 种物品不同的策略写出状态转移方程,像这样: ? f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

? ? ? ?

这跟01背包问题一样有O(N*V)个状态需要求解,但求解 每个状态的时间已经不是常数了,求解状态f[i][v]的时间 是O(v/c[i]),总的复杂度是超过O(VN)的。 我们有更优的O(VN)的算法。 O(VN)的算法 这个算法使用一维数组,先看伪代码: for i=1..N for v=0..V f[v]=max{f[v],f[v-cost]+weight} 你会发 现,这个伪代码与01背包的伪代码只有v的循环次序不同 而已。为什么这样一改就可行呢?

? 首先想想为什么01背包中要按照v=V..0的逆序来循环。这 是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][vc[i]]递推而来。换句话说,这正是为了保证每件物品只选 一次,保证在考虑“选入第i件物品”这件策略时,依据 的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。 而现在完全背包的特点恰是每种物品可选无限件,所以在 考虑“加选一件第i种物品”这种策略时,却正需要一个 可能已选入第i种物品的子结果f[i][v-c[i]],所以就可以并 且必须采用v=0..V的顺序循环。这就是这个简单的程序为 何成立的道理。

? 总分 ? 学生在我们USACO的竞赛中的得分越多我们越高兴。 我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮 助。 我们可以从几个种类中选取竞赛的题目,这里的一个"种类"是指一个 竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相 同的分数。 你的任务是写一个程序来告诉USACO的职员,应该从每一个种类中选 取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最 大。 输入包括竞赛的时间,M(1 <= M <= 10,000)(不要担心,你要到了训练 营中才会有长时间的比赛)和N,"种类"的数目1 <= N <= 10,000。 后面的每一行将包括两个整数来描述一个"种类": 第一个整数说明解决这种题目能得的分数(1 <= points <= 10000),第 二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。 你的程序应该确定我们应该从每个"种类"中选多少道题目使得能在竞 赛的时间中得到最大的分数。 来自任意的"种类"的题目数目可能任何非负数(0或更多)。 计算可能得到的最大分数。

? PROGRAM NAME: inflate ? INPUT FORMAT ? 第 1 行:M, N--竞赛的时间和题目"种类"的数目。 第 2-N+1 行: 两个整 数:每个"种类"题目的分数和耗时。SAMPLE INPUT (inflate.in) ? 300 4 100 60 250 120 120 100 35 20 ? OUTPUT FORMAT ? 单独的一行包括那个在给定的限制里可能得到的最大的分数。 ? SAMPLE OUTPUT ( inflate.out) ? 605 {从第2个"种类"中选两题第4个"种类"中选三题}

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

const maxtime=10000; var score:array[0..maxtime] of longint; m,n,p,t,i,j:longint; begin assign(input,'inflate.in');reset(input); assign(output,'inflate.out'); rewrite(output); read(m,n); for i:=1 to n do begin read(p,t); for j:=t to m do if score[j-t]+p>score[j] then score[j]:=score[j-t]+p; end; writeln(score[m]); close(input); close(output); end.

? 多重背包问题
题目 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用, 每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物 品的费用总和不超过背包容量,且价值总和最大。 基本算法 这题目和完全背包问题很类似。基本的方程只需将完全背包问题的 方程略微一改即可,因为对于第i种物品有n[i]+1种策略:取0件, 取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背 包的最大权值,则有状态转移方程: f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]} 复杂度是O(V*Σn[i])。 转化为01背包问题
另一种好想好写的基本方法是转化为01背包求解:把第i种物品换成n[i] 件01背包中的物品,则得到了物品数为Σn[i]的01背包问题,直接求解,复 杂度仍然是O(V*Σn[i])。

? ? ? ? ? ? ? ?

? 砝码称重fama.pas 设有1g、2g、3g、5g、10g、20g的砝码各若干枚(其总重<=1000), 要求: 输入方式:a1 a2 a3 a4 a5 a6 (表示1g砝码有a1个,2g砝码有a2个,…,20g砝码有a6个) 输出方式:Total=N (N表示用这些砝码能称出的不同重量的个数,但不包括一个砝码也 不用的情况) 如输入:1_1_0_0_0_0 (注:下划线表示空格)(fama.in) 输出:3 表示可以称出1g,2g,3g三种不同的重量。(fama.out)

? assign(input,'fama.in');reset(input); ? assign(output,'fama.out');rewrite(output); ? for i:=1 to 6 do begin ? read(w[i]); 把第i种物品换成n[i]件01背 ? n:=n+w[i]*v[i]; 包中的物品 ? end; ? fillchar(f,sizeof(f),0);s:=0; ? f[0]:=true; ? for i:=1 to 6 do ? for j:=n downto 0 do ? for k:=1 to w[i] do ? if j>=v[i]*k then f[j]:=f[j] or f[j-v[i]*k]; ? for i:=1 to n do if f[i] then inc(s); ? writeln(s); ? close(input);close(output);

如果k与j位置互换,则程序如下:
? assign(input,'fama.in');reset(input); ? assign(output,'fama.out');rewrite(output); ? for i:=1 to 6 do begin ? read(w[i]); ? n:=n+w[i]*v[i]; ? end; 转成完全背包问题,状态不一样 ? fillchar(f,sizeof(f),0);s:=0; ? f[0]:=true; ? for i:=1 to 6 do ? for k:=1 to w[i] do ? for j:=n downto v[i]*k do ? f[j]:=f[j] or f[j-v[i]]; ? for i:=1 to n do if f[i] then inc(s); ? writeln(s); ? close(input);close(output);



更多相关文章:
背包问题
背包问题_理学_高等教育_教育专区。定义我们有 n 种物品,物品 j 的重量为 wj...文档贡献者 zhangaimin1228 贡献于2012-02-11 1/2 相关文档推荐...
背包问题算法
背包问题算法_IT/计算机_专业资料。背包问题是算法的传统问题,该文分析了背包问题...文档贡献者 demonst2011 贡献于2012-03-19 1/2 相关文档推荐 背包问题的实用...
01背包问题动态规划详解
01背包问题动态规划详解_计算机软件及应用_IT/计算机_专业资料。01背包问题动态...文档贡献者 8554268 贡献于2012-07-27 1/2 相关文档推荐 利用动态规划解决01...
0-1背包问题c++版
0-1背包问题c++版_计算机软件及应用_IT/计算机_专业资料。用动态规划法解决0-...文档贡献者 HaiDiZhiWa 贡献于2012-10-30 1/2 相关文档推荐 遗传算法的0-1...
算法分析与设计-贪心算法求解背包问题
《算法分析与设计》 1 用贪心算法求解背包问题 D 软件 101 薛思雨 511020825 ...文档贡献者 vampire_yoo 贡献于2012-06-23 1/2 相关文档推荐 ...
01背包较好理解的讲解
动态规划之 01 背包问题(最易理解的讲解) 分类: 01 背包动态规划 2012-07-06 17:09 31770 人阅读评论(13) 收藏举报 算法 c 01 背包问题, 是用来介绍动态...
算法实验报告01背包问题
算法实验报告01背包问题_工学_高等教育_教育专区。hebut的,你懂得。动态规划、贪心...文档贡献者 心零影碎 贡献于2012-06-12 1/2 相关文档推荐 算法设计与分析...
利用动态规划求解0-1背包问题
利用动态规划求解0-1背包问题_计算机软件及应用_IT/计算机_专业资料。算法分析与...文档贡献者 yz2437 贡献于2012-04-27 1/2 相关文档推荐 0-1背包问题动态...
用遗传算法解决0-1背包问题
实现遗传算法的 0-1 背包问题 求解及其改进 姓名: 学号: 班级: 提交日期:2012 年 6 月 27 日 实现遗传算法的 0-1 背包问题求解摘要:研究了遗传算法解决 0...
01背包问题动态规划详解及C++代码
01背包问题动态规划详解及C++代码_计算机软件及应用_IT/计算机_专业资料。0/1 ...文档贡献者 s1042280654 贡献于2012-12-23 1/2 相关文档推荐 利用动态规划解决...
更多相关标签:
背包问题    0 1背包问题    背包问题 动态规划    01背包问题动态规划    01背包问题贪心算法    回溯法 0 1背包问题    01背包问题分支限界法    回溯法解决01背包问题    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图