给出 n 个物品，第 i 个物品有重量 w i 。现在有 m 个背包，第 i 个背包的限重为 c i ，求最少用几个背 包能装下所有的物品。
Input
输入的第一行两个整数 n, m ( n ≤ 24 , m ≤ 100) 。
接下来一行 n 个整数，描述 w ( w i ≤ 10^8 ) 。
接下来一行 m 个整数，描述 c ( c i ≤ 10^8 ) 。
Output
输出一行一个整数，描述最少需要使用的背包数。如果没有可行的方案来装下所有物品，请输出”NIE” （不含引号）。
题解：O(∩_∩)O谢谢出这套题目的学长，题目出的很好，好了，对于这个题目，因为我们要选择几个信息或者说记住几个特征，既可以描述所以的状态又方便转移，显然这个题状态很直接，我们显然要记住这个序列的所有物品是否被选，还要记住，当前用了几个背包，
还要知道当前的背包还剩多少，所有可以状压一个2进制数i表示那些物品是否被选，设dp[i]表示要装下i最少要多少个背包，然后rest[i]
表示用了dp[i]个背包后还有一部分剩下的重物放在第dp[i]+1个背包的重量，那么转移就是显然的了。注意我是用记忆化搜索，如果dp[i]<n说明这个状态已经算过了，就可以直接返回了。
代码：
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<algorithm> #include<cstring> using namespace std; short dp[16777217];int use[16777217]; int wu[110],bao[110],n,m,inf; void cl(){ memset(wu,0,sizeof(wu)); memset(bao,0,sizeof(bao)); memset(dp,127,sizeof(dp)); memset(use,127,sizeof(use)); inf=use[0]; } bool comp(int x,int y){ if(x>y) return 1; return 0; } void dfs(int x){ if(dp[x]<n) return; int q=inf,p=inf; for(int now=1;now<=n;now++){ if(x&(1<<(now-1))){ int r=x-(1<<(now-1)); dfs(r); if(bao[dp[r]+1]-use[r]>=wu[now]) q=dp[r],p=use[r]+wu[now]; else if(bao[dp[r]+1]>=wu[now]&&bao[dp[r]+2]>=wu[now]) q=dp[r]+1,p=wu[now]; else continue; if(q<dp[x]) dp[x]=q,use[x]=p; else if(q==dp[x]&&p<use[x]) use[x]=p; } } } int main(){ cl(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&wu[i]); for(int i=1;i<=m;i++) scanf("%d",&bao[i]); sort(wu+1,wu+n+1,comp); sort(bao+1,bao+m+1,comp); if(bao[1]<wu[1]) {printf("NIE");return 0;} dp[0]=use[0]=0; dfs((1<<n)-1); if(dp[(1<<n)-1]>m) printf("NIE"); else printf("%d",dp[(1<<n)-1]+(use[(1<<n)-1]>0)); return 0; }