思路：直接引用论文的话。
暂时先不考虑“使剩下的物品都放不下”的条件，那就是求 0-1 背包
的所有可行方案。
用 Fi[j]表示前 i 件物品中选若干件总体积为 j 的方案数，初始为 F0[0]=1，转移
方程是：
Fi[j] = Fi-1[j] (Vi>j)
Fi[j] = Fi-1[j] + Fi-1[j-Vi](j>=Vi)
显然这个算法的效率是 O(n*C)的，它计算了所有装放背包的方案数。
现在考虑“使剩下的物品都放不进去”的条件，如果剩下的物品中体
积最小为 v，那么方案数就是 sum{ Fn[j] }(C>=j>C-v)。前提是我们事先确定
了剩下中体积最小的是哪个。
对体积排序后，下一步就是枚举 i 作为剩余物品中体积最小的一件。对
于所有 s<i 的物品必须都要放入背包，对于 i 则不能放入背包，对于 s>i 的
物品做 0-1背包可行方案的统计，将sum{ Fn[j] }(C>=j>C-Vi)累加到 ans。
由于每次都需要对 n-i 件物品做统计，一共统计 n次，效率是 O(n2
*C)。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #define Maxn 4000 using namespace std; int v[Maxn],dp[10100],ans,Min,Sum; int main() { int t,n,m,i,j,Case=0; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); Sum=0; Min=0x7fffffff; for(i=1;i<=n;i++) { scanf("%d",v+i); Min=min(Min,v[i]); Sum+=v[i]; } ans=0; int sum=0,f=0,k; sort(v+1,v+1+n); for(i=1;i<=n;i++) { memset(dp,0,sizeof(dp)); dp[sum]=1; for(j=i+1;j<=n;j++) for(k=m;k>=sum+v[j];k--) dp[k]=dp[k]+dp[k-v[j]]; for(j=m;j>=m-v[i]+1;j--) if(j>=sum) ans+=dp[j]; sum+=v[i]; } if(Sum<=m) printf("%d 1 ",++Case); else if(Min>m) printf("%d 0 ",++Case); else printf("%d %d ",++Case,ans); } return 0; }