Old Wine Into New Bottles 2614.ppt

《Old Wine Into New Bottles 2614.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、OldWineIntoNewBottlesPoj2614高照00748034Description有W升百年藏酿的美酒，需要把它们分装在一些酒瓶中。这些酒瓶有n种不同的大小。每种大小的酒瓶都有无数个。任意一种酒瓶都有容量的上限和下限，即如果选择用酒瓶i，则i中至少装miniml酒，至多装maximl酒。酒很珍贵！要用给出的酒瓶装尽可能多的酒。output最少剩余酒的ml数。BottleslowhighminmaxdeltaSomeLimits0<=w<=1,000,000L1<=n<=100max*95%<=min<=max*99%&325m

2、l<=max<=4500ml（输入时的条件）BecarefulExamplesInput10244504500725750Output250Input（2）10000244504500725750Output（2）0样例分析Input1:W=10*1000=10,000W/4500=2······10001000/750=1······250orW=750*10+250Input2:W=10,000,000······样例分析事实上，从样例看出，若选择k个瓶子，则它们有容积下限h1:与容积上限h2:样例分析若酒的总量W在区间[h1，h2]内，

3、则必可被完全装满。否则求出最大的h2，W–h2即为最少剩余的酒量。背包问题有n个物品和一个背包，对于i=1，2，···，n，物品i有正的重量wi和正的价值vi，背包可携带的重量不超过W。目标是，在不超过背包负重的前提下，使得装入背包的物品总价值最大。背包问题的一些算法贪婪算法（适合于物品可分割成更小块）按单位重量价值大到小的先后顺序装入背包，得到最优解。背包问题的一些算法动态规划建立一张表V[i，j]，表的行表示每种可用的物品，列表示从0到W的每个重量。V[i，j]表示若总重量限制是j，而且只能用标号为1~i的物品时，能得到的最大总价值。V[

4、i，j]=max{V[i-1,j],V[i-1,j-wi]+vi}例wi=1，2，5，6，7vi=1，6，18，22，28(wi,vi)01234567891011(1,1)011111111111(2,6)016777777777(5,18)0167718192425252525(6,22)0167718222428282940(7,28)0167718222829343540回溯法假设希望求解包含4种物品的背包问题的一个实例。wi=2，3，4，5vi=3，5，6，10背包最大载重W=8回溯法求解类似深度优先搜索。背包实例的隐含树；02；3

5、3；54；65；102,2；62,3；82,5；132,4；92,2,2；92,2,3；112,2,4；122,3,3；132,2,2,2；124,4；123,5；153,4；113,3；10回溯算法实现intbackpack(i,left){b=0；for(k=i;k<=n;k++){if(w[k]<=left)b=max(b,v[k]+backpack(k,left-w[k]))；returnb;}}背包问题另外，背包问题的一些近似算法，ms比较深奥，我们先不去讨论它们了。Compare贪婪算法适用于物品可微分的情况，对于物品不可微的问题

6、，贪婪算法将不起作用。Compare动态规划的优点是节约时间，但是对于10e9这样的规模，将会耗费很大空间。Compare回溯法要费时一些，但是可能对于大的数据，使用回溯的思想比较合适。当然，我们还可以作一些优化。2614下面我们考虑用回溯的思想来解决wine&bottles的问题。Oldwineintonewbottle回顾一下，前面我们曾设h1=h2=Oldwineintonewbottle回溯思想说，对于2614，我们可以先选择一种瓶子去装酒，直到达到其上界，然后换掉一个瓶子，依次类推，找到一个包含W的区间[h1，h2]，或求得最大的h

7、2。考虑用一数组模拟装酒的过程。数组总长度即为W。先来看看只使用一种瓶子的情况。过程相当于把数组从左端开始分为长度为high的若干段，直至无法再分。每一段都表示一个瓶子。1234……WOldwineintonewbottle进一步研究一下每个瓶子。我们发现最后一个瓶子可以分为两部分：low’与d。其中，d的那部分是可选的，即若最后的瓶子在数组中的h1<=W，h2>=W时，当然可将W装完。Oldwineintonewbottle…h1Wlow’dhighh2考虑如何确定d。对于若干个瓶子，它们的总的可选容积应在最后一段体现出来。即应在最后部分表

8、示出每个瓶子的d之和。Oldwineintonewbottle…h1Wlow’dhighOldwineintonewbottle于是我们可对数组进行如下分割及赋值。