思路：直接引用论文的话。
暂时先不考虑“使剩下的物品都放不下”的条件，那就是求 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[],ans,Min,Sum;
int main()
{
int t,n,m,i,j,Case=;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
Sum=;
Min=0x7fffffff;
for(i=;i<=n;i++)
{
scanf("%d",v+i);
Min=min(Min,v[i]);
Sum+=v[i];
}
ans=;
int sum=,f=,k;
sort(v+,v++n);
for(i=;i<=n;i++)
{
memset(dp,,sizeof(dp));
dp[sum]=;
for(j=i+;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]+;j--)
if(j>=sum) ans+=dp[j];
sum+=v[i];
}
if(Sum<=m)
printf("%d 1\n",++Case);
else
if(Min>m)
printf("%d 0\n",++Case);
else
printf("%d %d\n",++Case,ans);
}
return ;
}