题意:有多个饼干,每个饼干有一定的数量,也有一定的能量,也有一定的体积。有多个卡车,每一辆卡车有一定的容积,用这辆车需要一定的费用,有一定的数量。

现在需求的能量为p。问需要最少多少费用,可以承载能量为p的饼干,注意,一个饼干可以拆分到别的卡车。

思路:先用一次多重背包来跑出最小的体积。这个应该很明显的。

得出最小的体积来之后,我又跑了一遍多重背包,求出在这个体积下的最小的费用。

但是超时了。想一下,最小的体积高达5 * 10^5,然后乘上n(100),再乘上多重背包的常数,然后就无情超时了。

其实这个优化是很简单的。注意后面给出的是费用超过50000就不计算,也就是通过这个点优化,计算出 在 i 费用下的最大容积,与得出的最小体积比较一下即可。

这样复杂度 大概也就是 5*10^4 乘上 n(100),再乘上多重背包的系数,足足少了一个常数10啊!

 

 

HDU 5410 CRB and His Birthday(01背包和完全背包)

题意:有一个背包w。有n件物品价值是变动的a*k+b,问你如何让总价值最大。 思路:很长时间没有写背包了。都快忘干净了。 赶紧写一发题解压压惊。 如果这个题...

阅读全文

ZOJ 3812 We Need Medicine(状态压缩式的01背包)

题意:给定n种要药品,有两个属性(x,y), 现在有m种病毒,有两个属性(a,b),问对于任何一个(a,b)是否可以由其中的(x,y)相加得来。对于每一种药品...

阅读全文

省赛题目 Pick apples(完全背包)

这个背包题目还是可以的、 http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2408 首先是一步简单的贪心思想。试想。 当背包的...

阅读全文

2 条评论

欢迎留言

*