北航算法第三次练习赛-零崎的补番计划Ⅱ | Eternal_zttz

北航算法第三次练习赛-零崎的补番计划Ⅱ

致敬DP

1. 解题思路

这一题就是一道裸的01背包问题,直接套用01背包模版即可。
01背包是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。
如果我们用子问题来定义状态:即f[i,j]表示前i件物品恰好放入一个容量为j的背包可以获得的最大价值。那么它的状态转移方程便是:

1
f[i,j] = max(f[i-1,j],f[i-1,j-w[i]]+ v[i]);

这个状态转移方程是最基本的背包转移方程。它所表达的意思便是:

我们要求把i个物品放到容量为j的背包中这个问题,如果只考虑第i件物品(要么放,要么不放),那么就可以转化为一个只和前i-1件物品相关的问题。如果不放第i件物品,那么问题就变成了“前i-1件物品放入容量为j的背包中”,价值为F[i-1][j];如果放第i件物品,那么问题就转化为“前i-1件物品放入容量为j-w[i]的背包中”,此时得到的最大价值就是F[i-1,j-w[i]],再加上通过放入第i件物品获得的价值v[i].

核心代码如下:

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

时间复杂度为

空间优化:
通过观察我们可以发现,求解第i个子问题,它只和第 i-1个子问题有关,和之前的问题没有直接的关系,那么,毫无疑问,使用二维数组我们会浪费很多的空间。在这里,我们可以使用滚动数组将二维转化为一维数组求解。

注意这时候我们需要逆序循环第二维。

为什么呢?我们想想f[]数组的意义:在某个i下,f[j]表示的是当前背包容量为j时的最大值,所以在我们开始循环i时,由于还未开始循环,此时f[i]保存的是前一次 i -1 时背包的价值,即此时f[j]对应于f[i-1][j]],那么很明显:
我们求解时:f[j] = max(f[j],f[j-w[i]]+v[i]);
对应的就是:f[i][j] =max(f[i-1][j],f[i-1][j-w[i]]+v[i]);

核心代码为:

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

时间复杂度为

##2. AC代码 ##

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

空间优化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
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 = t;j>=w[i];j--){
f[j] = max(f[j],f[j-w[i]]+v[i]);
}
}
printf("%d\n",f[t]);
}
}

-------------The End-------------