北航算法第三次练习赛- DP大作战—多重背包 | Eternal_zttz

北航算法第三次练习赛- DP大作战—多重背包

致敬DP

解题思路

这是一道多重背包的模版题,多重背包和完全背包问题很类似,基本的方程只需将完全背包问题的方程略微改改即可。

我们可以看到,对于第i种物品如果件数为num[i],那么便有num[i]+1种策略:取0件,取1件…..取num[i]件。令f[i,j]表示前i种物品恰好放入一个容量为j的背包的最大价值,那么状态转移方程即为:

1
f[i,j] = max(f[i-1,j-k*w[i]]+k*v[i])    (0<=k<=num[i])

这种写法可能比较难以想到,实际上,对于多重背包而言,我们依旧可以使用01背包的方式来编写代码:即把第i种物品换成num[i]件01背包的物品,直接求解即可。

使用01背包的想法当然可以求解,然而,对于时间复杂度而言,使用01背包显然并没有提升,那么可不可以如完全背包一样降低时间复杂度呢?

当然是可以,我们考虑二进制的思想,把第i种物品换成若干件01背包中的物品,其中每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。令这些系数分别为1,2,2^2,…..2^(k-1),num[i] - 2^k+1,且k是满足num[i] - 2^k +1>0的最大整数。例如,如果num[i] = 13,那么这种最多取13件的物品应被分成系数分别为1,2,4,6的四件物品。

使用这种方式的好处就在于,我们大大减少了分配物品的数量,假如是一件一件分配的话,那么很明显需要13件,然而现在只需要4件,时间复杂度可以大大减低。

另外,我们同时也保证的代码的正确性,使用这种方式我们可以覆盖0…num[i]之间的任何一个整数,无论最终我们采取的是选择这种物品几件,都会有一个答案。正确性的证明可以分为0….2^k-1 和 2^k…num[i]两段考虑,在这里不做累赘。

那么核心代码便是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void mutil(int weight,int value,int count){
int k;
if(weight*count >=x){//如果大于,这里便可以当成完全背包考虑。
complete(weight, value);
return;
}
k = 1;
while(k<count){//对系数为2^n的项进行01背包
zero(k*weight, k*value);
count -= k ;
k *= 2;
}
zero(weight*count, value*count);//对最后一项进行01背包
}

具体代码可看下方:

AC 代码

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
#include <cstdio>
#include <algorithm>
#include <algorithm>
using namespace std;

#define M 1000010
#define N 1000
int v[N],w[N],c[N],f[M],x;

void zero(int weight,int value){
for (int j = x;j>=weight;j--)
f[j] = max(f[j],f[j-weight]+value);
}

void complete(int weight,int value){
for (int j = weight;j<=x;j++)
f[j] = max(f[j],f[j-weight]+value);
}

void mutil(int weight,int value,int count){
int k;
if(weight*count >=x){
complete(weight, value);
return;
}
k = 1;
while(k<count){
zero(k*weight, k*value);
count -= k ;
k *= 2;
}
zero(weight*count, value*count);
}

int main(){
int n,num;
scanf("%d",&n);
while(n --){
scanf("%d %d",&x,&num);
for (int i = 0;i<num;i++)
scanf("%d %d %d",&v[i],&w[i],&c[i]);
for (int k = 0;k<num;k++)
mutil(w[k], v[k], c[k]);
printf("%d\n",f[x]);
}
return 0;
}
-------------The End-------------