[题解]2019.11.5 背包
题意
给定一个01背包和n个物品，背包的容积为k，求有多少种选择方法使得背包再也放不下余下的任意物品。
分析
此题用动规做法，用f[j]表示装满j体积的方案数，那么因为要求的是求不能再放下其他物品的方案数，假设第i个物品为不能放下的物品中体积最小的，那么体积比第i个物品还小的肯定都已经放入了背包中，因为此时背包不能放下第i个物品，所以背包还剩余的体积有可能是0到v[i]-1，这样的话只需要计算出用比v[i]大的物品填满k-(比v[i]小的物品的体积总和)-j(j从0-v[i]-1枚举)的空间的方案数就行了。
到这一步大概已经看出，使用这样的算法需要用排序来使v[i]数组有序，我们从小到大排序后，从后向前枚举i，这样就可以保证在跑用比v[i]大的物品装满j体积空间是无后效性（不太好懂的话可以看看代码辅助理解），同时用一个sum保存前i-1个物品的体积和来提高效率（sum的初始值为所有物品的总和，每枚举到一个i，sum-=v[i]就可以使sum记录的是前i-1个物品的体积和）。
这部分的代码如下
累计答案
1
2
3
4
| for(int j=0;j<v[i]&&k-sum-j>=0;j++)
{
ans+=f[k-sum-j];
}
|
状态转移
1
2
3
4
| for(int j=k;j>=v[i];j--)
{
f[j]+=f[j-v[i]];
}
|
代码
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<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,k;
int v[1010],f[1010];
int ans,sum;
int main()
{
#ifndef WDC
freopen("problem.in","r",stdin);
freopen("problem.out","w",stdout);
#endif
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
sum=0;
ans=0;
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
sum+=v[i];
}
f[0]=1;
sort(v+1,v+n+1);
for(int i=n;i>=1;i--)
{
sum-=v[i];
for(int j=0;j<v[i]&&k-sum-j>=0;j++)
{
ans+=f[k-sum-j];
}
for(int j=k;j>=v[i];j--)
{
f[j]+=f[j-v[i]];
}
}
printf("%d\n",ans);
}
#ifndef WDC
fclose(stdin);
fclose(stdout);
#endif
return 0;
}
|