稍微复杂一些的0、1背包，要把背包尽可能装满，直到再也装不下任何物品，求总装法。这题是不用考虑W的，先把V升序排序，从小到大枚举，当前物品为剩下未使用的物品中体积最小的，那么比当前小的一定是要使用的。这种思路是n^3的，后面的物品会被重复计算，如果从后往前枚举就能避免这个问题，复杂度为n^2。
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 int dp[1005],sum[35],w[35]; 6 int main() 7 { 8 int T,m,n,v,i,j,k,ans; 9 scanf("%d",&T); 10 for(m = 1; m <= T; m++) 11 { 12 scanf("%d%d",&n,&v); 13 for(i = 1; i <= n; i++) 14 scanf("%d",&w[i]); 15 sort(w+1,w+1+n); 16 if(w[1] > v) 17 { 18 printf("%d 0\n",m); 19 continue; 20 } 21 ans = 0; 22 sum[0] = 0; 23 for(i = 1; i <= n; i++) 24 sum[i] = sum[i-1] + w[i]; 25 memset(dp,0,sizeof dp); 26 dp[0] = 1; 27 for(i = n; i >= 1; i--) 28 { 29 k = max(0,v-sum[i]+1); 30 for(j = v-sum[i-1]; j >= k; j--) 31 if(dp[j]) ans += dp[j]; 32 for(j= v; j >= w[i]; j--) 33 dp[j] += dp[j - w[i] ]; 34 } 35 printf("%d %d\n",m,ans); 36 } 37 return 0; 38 }