《Old Wine Into New Bottles 2614.ppt》由会员分享，可在线阅读，更多相关《Old Wine Into New Bottles 2614.ppt（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Old Wine Into New BottlesPoj 2614高照高照0074803400748034Description 有W升百年藏酿的美酒，需要把它们分装在一些酒瓶中。这些酒瓶有n种不同的大小。每种大小的酒瓶都有无数个。任意一种酒瓶都有容量的上限和下限，即如果选择用酒瓶 i，则 i 中至少装mini ml酒，至多装maxi ml酒。酒很珍贵！要用给出的酒瓶装尽可能多的酒。output最少剩余酒的ml数。BottleslowhighminmaxdeltaSome Limits0=w=1,000,000 L1=n=100max*95%=min=max*99%&325 ml=max=45
2、00 ml（输入时的条件）Be carefulExamplesInput 10 24450 4500725 750Output250Input （2）10000 24450 4500725 750Output （2）0样例分析样例分析Input 1:Input 1:W=10*1000=10,000W=10*1000=10,000W/4500=2 1000W/4500=2 10001000/750=1 2501000/750=1 250 or orW=750*10+250W=750*10+250Input 2:Input 2:W=10,000,000W=10,000,000 样例分析样例分析事实
3、上，从样例看出，若选择k个瓶子，则它们有 容积下限 h1:与容积上限 h2:样例分析样例分析若酒的总量W在区间 h1，h2 内，则必可被完全装满。否则求出最大的 h2，W h2 即为最少剩余的酒量。背包问题背包问题有n个物品和一个背包，对于i=1，2，n，物品i有正的重量wi和正的价值vi，背包可携带的重量不超过W。目标是，在不超过背包负重的前提下，使得装入背包的物品总价值最大。背包问题的一些算法背包问题的一些算法贪婪算法（适合于物品可分割成更小块）按单位重量价值大到小的先后顺序装入背包，得到最优解。背包问题的一些算法背包问题的一些算法动态规划 建立一张表V i，j，表的行表示每种可用的物品，
4、列表示从0到W的每个重量。V i，j表示若总重量限制是 j，而且只能用标号为1i 的物品时，能得到的最大总价值。V i，j=max V i-1,j ,Vi-1,j-wi +vi 例例例例 wiwi=1=1，2 2，5 5，6 6，7 vi=17 vi=1，6 6，1818，2222，2828(wi,wi,vi vi)0 01 12 23 34 45 56 67 78 89 910101111(1,1(1,1)0 01 11 11 11 11 11 11 11 11 11 11 1(2,6(2,6)0 01 16 67 77 77 77 77 77 77 77 77 7(5,1(5,18)8)0
5、 01 16 67 77 71818191924242525252525252525(6,2(6,22)2)0 01 16 67 77 71818222224242828282829294040(7,2(7,28)8)0 01 16 67 77 71818222228282929343435354040回溯法回溯法假设希望求解包含4种物品的背包问题的一个实例。wi=2，3，4，5vi =3，5，6，10背包最大载重 W=8 回溯法求解类似深度优先搜索。背包实例的隐含树背包实例的隐含树；02；33；54；65；102,2；62,3；82,5；132,4；92,2,2；92,2,3；112,2,4
6、；122,3,3；132,2,2,2；124,4；123,5；153,4；113,3；10回溯算法实现回溯算法实现intint backpack(i,left)backpack(i,left)b=0b=0；for(k=i;k=n;k+)for(k=i;k=n;k+)if(w k =left)if(w k =left)b=max(b,b=max(b,vkvk+backpack(k,left-w k)+backpack(k,left-w k)；return b;return b;背包问题背包问题另外，背包问题的一些近似算法，ms比较深奥，我们先不去讨论它们了。Compare贪婪算法适用于物品可微分
7、的情况，对于物品不可微的问题，贪婪算法将不起作用。Compare动态规划的优点是节约时间，但是对于10e9这样的规模，将会耗费很大空间。Compare回溯法要费时一些，但是可能对于大的数据，使用回溯的思想比较合适。当然，我们还可以作一些优化。2614下面我们考虑用回溯的思想来解决wine&bottles的问题。Old wine into new bottle回顾一下，前面我们曾设 h1=h2=Old wine into new bottle回溯思想说，对于2614，我们可以先选择一种瓶子去装酒，直到达到其上界，然后换掉一个瓶子，依次类推，找到一个包含W的区间 h1，h2，或求得最大的h2。考虑
8、用一数组模拟装酒的过程。考虑用一数组模拟装酒的过程。数组总长度即为数组总长度即为WW。先来看看只使用一种瓶子的情况。过程相当于把先来看看只使用一种瓶子的情况。过程相当于把数组从左端开始分为长度为数组从左端开始分为长度为highhigh的若干段，直至的若干段，直至无法再分。每一段都表示一个瓶子。无法再分。每一段都表示一个瓶子。1 12 23 34 4 WWOld wine into new bottle进一步研究一下每个瓶子。我们发现最后一个瓶子可以分为两部分：low 与 d。其中，d 的那部分是可选的，即若最后的瓶子在数组中的h1=W时，当然可将W装完。Old wine into new bo
9、ttleh1h1WWlow dhighh2考虑如何确定d。对于若干个瓶子，它们的总的可选容积应在最后一段体现出来。即应在最后部分表示出每个瓶子的d之和。Old wine into new bottleh1h1WWlow dhighOld wine into new bottle于是我们可对数组进行如下分割及赋值。于是我们可对数组进行如下分割及赋值。1 1表示该部分可选，表示该部分可选，0 0表示不可选。将中间的表示不可选。将中间的d d也都也都累加是为了确定最后一段的累加是为了确定最后一段的d d。并且这样也将利于。并且这样也将利于用代码实现。用代码实现。0 01 10 01 11 10 01 1highhighlowLowd2dkdhighOld wine into new bottle实现过程：ar 0=1；for(i=0;i=W low;i+)if(ar i=1)x=0;else x+;if(x=h2,酒均可被全部装完。Detailsproblem：maxh2 =？Old wine into new bottle450000？。500000？。至此，题目的讨论就接近尾声了。Old wine into new bottleThanks！Old wine into new bottle