北航算法第三次练习赛-零崎的朋友很多Ⅰ | Eternal_zttz

北航算法第三次练习赛-零崎的朋友很多Ⅰ

致敬DP

1. 解题思路

这是一道完全背包问题,非常类似于01背包问题,不同的地方在于每种物品有无限件,也就是说,从每种物品的角度考虑,与它相关的策略已并非取或是不取,而是有取0件,取1件,取2件….直到取V/w[i]件等许多种。

如果仍然按照01背包时的思路,令F[i,j]表示前i种物品恰放入一个容量为v的背包的最大权值。那么可以按照每种物品不同的策略写出状态转移方程:

1
f[i,j] = max(f[i-1,v-kw[i]+kw[i]) (0<=kw[i]<=v)

这和01背包问题一样有O(VN)个状态需要求解,但是求解每个状态的时间已经不是常数了,对于状态f[i][j]而言,求解的时间是O(v/w[i]),时间复杂度大于O(VN)

其实,对于完全背包,最容易想到的做法 便是将它转化成01背包求解。我们考虑到第i种物品最多选V/w[i]件,那么我们完全可以把第i种物品转化为[V/w[i]]件费用及价值均不变的物品,然后求解这个01背包问题。这虽然没有降低它的时间复杂度,但是,确能够有一个清晰的方法来求解问题。

完全背包的优化:
和01背包一样,完全背包也可以使用一维数组来求解:
我们来看看核心代码:

1
2
3
4
5
6
for (int i = 0;i<k;i++){
for (int j = w[i];j<=t;j++){
if(f[j]<f[j-w[i]]+v[i])
f[j] = f[j-w[i]]+v[i];
}
}

稍加观察我们就可以发现,和01背包唯一不同的是对V遍历时变为正序。

01背包中逆序是因为F[i][]只和F[i-1][]有关,且第i件的物品加入不会对F[i-1][]状态造成影响。而完全背包则考虑的是第i种物品的出现的问题,第i种物品一旦出现它势必应该对第i种物品还没出现的各状态造成影响。

也就是说,原来没有第i种物品的情况下可能有一个最优解,现在第i种物品出现了,而它的加入有可能得到更优解,所以之前的状态需要进行改变,故需要正序。

2. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
#include <cstring>
const int N = 20010;
int v[N],w[N],f[N];
int main(){
int t,k;
while(~scanf("%d %d",&t,&k)){
memset(v, 0, sizeof(v));
memset(w, 0, sizeof(w));
memset(f, 0, sizeof(f));
for (int i = 0;i<k;i++)
scanf("%d %d",&v[i],&w[i]);
for (int i = 0;i<k;i++){
for (int j = w[i];j<=t;j++){
if(f[j]<f[j-w[i]]+v[i])
f[j] = f[j-w[i]]+v[i];
}
}
printf("%d\n",f[t]);
}
}
-------------The End-------------