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个物品的体积对应到2^i-1 的位置，由于是从大到小，所以不会覆盖原先信息。

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

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