[PA 2014]Pakowanie

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

题解

*因为数组开小了，导致调了一个多小时...

首先我们有贪心的思想就是背包肯定是从大往小选。

再接着由于物品数$n<=24$，我们可以拿来状压。

设$f[S]$表示当前物品集合为$S$，且当前背包所用容量为$f[S]$，$g[S]$为当前背包的编号，也就是背包数量。

那么每次我们可以枚举一个物品加进来，如果没有炸掉当前背包，就可以直接填进去，否则就要开一个新背包，如果连新背包都开不下，那么这个转移就是不合法的。（参考wfj_2048）

 //It is made by Awson on 2017.10.15

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <cmath>

 #include <stack>

 #include <queue>

 #include <vector>

 #include <string>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define sqr(x) ((x)*(x))

 #define lowbit(x) ((-(x))&(x))

 using namespace std;

 const int N = <<;

 const int INF = ~0u>>;

 void read(int &x) {

     char ch; bool flag = ;

     for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());

     for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());

     x *= -*flag;

 }

 int n, m, st[N+];

 int a[], c[];

 int f[N+], g[N+];

 bool comp(const int &q, const int &p) {

     return q > p;

 }

 void work() {

     read(n), read(m);

     memset(f, -, sizeof(f));

     for (int i = ; i < n; i++) read(a[i]), st[<<i] = i;

     for (int i = ; i <= m; i++) read(c[i]); sort(c+, c+m+, comp);

     for (int i = ; i < n; i++) if (a[i] <= c[]) f[<<i] = c[]-a[i], g[<<i] = ;

     for (int i = , lim = <<n; i < lim; i++) {

         if (f[i] == -) f[i] = g[i] = INF;

         for (int t = i, j = i-lowbit(t); t && j; t -= lowbit(t), j = i-lowbit(t)) {

             if (f[j] == INF) continue;

             int bit = st[lowbit(t)];

             int ff, gg;

             if (f[j] >= a[bit]) ff = f[j]-a[bit], gg = g[j];

             else ff = c[g[j]+]-a[bit], gg = g[j]+;

             if (ff < ) continue;

             if (gg < g[i]) f[i] = ff, g[i] = gg;

             else if (gg == g[i] && f[i] < ff) f[i] = ff;

         }

     }

     if (f[(<<n)-] == INF || g[(<<n)-] > m) printf("NIE\n");

     else printf("%d\n", g[(<<n)-]);

 }

 int main() {

     work();

     return ;

 }

秒客网