这题目的思路很巧妙，什么情况下剩下的所有物品都放不下呢？就是当前剩余物品中最小的那个也放不下。所以，先把物品按照容量从小到大排序，依次枚举当前背包为放不下的最小物品的情况。
对于当前物品i，必有1到i-1的所有物品都放进去，这时候比i大的物品谁放谁不放是不确定的。转换成0-1背包问题：把前i-1个物品都放进去以后，得到空间为tsum – sum[i-1]（前缀和）的包，只要从第i+1到第n个物品中拿出一个方案填充这个包使得剩余体积小于第i个物品的体积就可以了，把总方案数累加就是结果！
注意特殊情况：当排序后最小的物品也无法放入时，直接返回0，因为dp[0]初始化为1,
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include<cstdio>
#include<algorithm>
#include<iostream>
#define MAXN 1005
using namespace std;
int n, m, wei[35], dp[MAXN], sum[MAXN];
__int64 Bag()
{
memset(sum, 0, sizeof(sum));
sort( wei + 1, wei + n + 1 );
if(wei[1] > m)
return 0;
for(int i = 1;i <= n;i ++)
sum[i] = sum[i-1] + wei[i];
__int64 ans = 0;
for(int i = 1;i <= n;i ++)
{
if(sum[i - 1] > m)
break;
memset(dp, 0, sizeof(dp));
dp[sum[i-1]] = 1;
for(int j = i + 1;j <= n;j ++)
for(int k = m; k >= sum[i - 1] + wei[j]; k --)
dp[k] += dp[k - wei[j]];
for(int j = m - wei[i] + 1;j <= m;j ++)
ans += dp[j];
}
return ans;
}
int main()
{
int Cases;
cin>>Cases;
for(int cnt = 1; cnt <= Cases; cnt ++)
{
cin >> n >> m;
for(int i = 1;i <= n;i ++)
cin>> wei[i];
cout << cnt << " " << Bag() <<endl;
}
return 0;
}
|