题意：多组输入，每组给定物品数(<=30)和背包容量(<=1000)以及接下来每个物品的体积，问有多少种方案，使得装入一些物品后，无法装入剩下的任意一个物品。 可以转化成01背包来做，首先按体积从小到大排序，枚举“剩下的物品”中体积最小的。剩下的物品中体积最小的为i时，前i-1个物品是必然被装入背包的，然后对第i+1到第n个物品做01背包,此时背包容量应为[m-v[i]+1,m] (保证连此时剩下的最小的i物品都放不下)，这样的话，由于第一次对（2，n）做01背包，第二次对(3,n)做01背包，每次都不得不重新做，复杂度是 O(n2m) 的。 我们可以考虑如下优化：我们能不能不每次都重做01背包？我们考虑倒着做，即 i从n到1，每次i为剩下的物品中体积最小的，则(1..i-1)应该都已经放在背包中了。而我们要对(i+1..n)做01背包。下次就是对(i..n)做01背包。发现没有！我们只是又多了一个物品i！这样我们就不需要每次都重做01背包了。我们只需每次在统计完答案后，把第i个物品放进背包。则下一次背包就已经是做好了的!这样就是 O(nm) 的了。
#include <cstdio> #include <cstring> #include <algorithm> #define ll long long #define N 1005 int v[31],n,tst,m,sum,f[N]; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } int main(){ // freopen("a.in","r",stdin); tst=read(); for(int tt=1;tt<=tst;++tt){ n=read();m=read();sum=0;ll ans=0; for(int i=1;i<=n;++i) v[i]=read(),sum+=v[i]; std::sort(v+1,v+n+1); memset(f,0,sizeof(f));f[0]=1; for(int i=n;i>=1;--i){ sum-=v[i];if(v[i]>m) continue; for(int j=0;j<v[i]&&m-sum-j>=0;++j)//j表示还差j装满m-sum。保证装不下v[i] ans+=f[m-sum-j]; for(int j=m;j>=v[i];--j) f[j]+=f[j-v[i]]; } printf("%d %lld\n",tt,ans); } return 0; }