Algorithm - DP - 背包

背包 (Knapsack) 是一类典型的动态规划模型.

完全背包

问题描述

有一个背包最大承载质量为 MM,现在 nn 种物品,第 ii 种物品的质量为 mim_i,价值为 viv_i,每种物品都有无限个,求能放的最大价值.

分析

可以建立 DAG,图的起点为 MM,终点任意,转化为求最长路.

代码

使用方法 infinite_knapsack(M, n, m, v)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstring>
#define MAXN (100000+5)
#define MAX(a,b) (((a)>(b))?(a):(b))
int d[MAXN];
int infinite_knapsack_sub(int capacity, int n, int *mass, int *rank)
{
if(d[capacity] != -1) return d[capacity];
d[capacity] = 0;
for(int i = 0; i < n; i++)
{
if(mass[i] <= capacity)
{
d[capacity] = MAX(d[capacity], infinite_knapsack_sub(capacity - mass[i], n, mass, rank) + rank[i]);
}
}
return d[capacity];
}
int infinite_knapsack(int capacity, int n, int *mass, int *rank)
{
memset(d, -1, sizeof(d));
return infinite_knapsack_sub(capacity, n, mass, rank);
}

0-1 背包

问题描述

有一个背包最大承载质量为 MM,现在 nn 种物品,第 ii 种物品的质量为 mim_i,价值为 viv_i,每种物品只有 11 个,求能放的最大价值.

分析

假设 d[j]d[j] 表示最大承载质量为 jj 时能放的最大价值,dd 全部初始化为 00.
那么对于第 ii 个物体来说,可以更新 j:mijM,d[j]=max{d[jmi]+vi,d[j]}\forall j: m_i \leqslant j \leqslant M, d[j] = \max\left\{d[j - m_i] + v_i, d[j]\right\}.

代码

使用方法 boolean_knapsack(M, n, m, v)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstring>
#define MAXN (100000+5)
#define MAX(a,b) (((a)>(b))?(a):(b))
int d[MAXN];
int boolean_knapsack(int capacity, int n, int *mass, int *rank)
{
memset(d, 0, sizeof(d));
for(int i = 0; i < n; i++)
{
for(int j = capacity; j >= mass[i]; j--)
{
d[j] = MAX(d[j - mass[i]] + rank[i], d[j]);
}
}
return d[capacity];
}

多重背包

问题描述

有一个背包最大承载质量为 MM,现在 nn 种物品,第 ii 种物品的质量为 mim_i,价值为 viv_i,数量有 aia_i 个,求能放的最大价值.

分析

个人一般是将多重背包转化为 0-1 背包,只需要将多个同种物品拆分为多种物品,即可转化为 0-1 背包.