bzoj3717: [PA2014]Pakowanie

Time Limit: 90 Sec Memory Limit: 256 MB
Submit: 128 Solved: 43
[Submit][Status][Discuss]
Description

你有n个物品和m个包。物品有重量,且不可被分割;包也有各自的容量。要把所有物品装入包中,至少需要几个包?

Input

第一行两个整数n,m(1<=n<=24,1<=m<=100),表示物品和包的数量。
第二行有n个整数a[1],a[2],…,a[n](1<=a[i]<=10^8),分别表示物品的重量。
第三行有m个整数c[1],c[2],…,c[m](1<=c[i]<=10^8),分别表示包的容量。

Output

如果能够装下,输出一个整数表示最少使用包的数目。若不能全部装下,则输出NIE。

Sample Input

4 3

4 2 10 3

11 18 9
Sample Output

2

状压dp
蛮恶心的,稍不注意就TLE

f[i]表示当前这个状态i最少需要用几个包,注意到,n<=24,容易发现,最多用n个包(虽然没什么意义),用体积大的包一定不比用体积小的包坏,所以先把包按体积从大到小排序,代码可以参考CreationAugust的  http://blog.csdn.net/creationaugust/article/details/50094881

我写几个注释。

for (int i=n;i;i--) a[(1<<(i-1))]=a[i];这里是为了方便,直接将第i个物品的体积对应到2i-1 的位置,由于是从大到小,所以不会覆盖原先信息。

lowbit的部分是按位取状态,表示判断当前这个物品能否从上一个状态加入转移到这个状态。

g[i]=-1是为了防止没有更新剩余空间为0的情况,所以外层还要特判g[i]为-1带来的影响bzoj3717: [PA2014]Pakowanie

上一篇:ural 1119. Metro(动态规划)


下一篇:Java常用工具类---XML工具类、数据验证工具类