完全背包问题
题目
有
N
N
N 种物品和一个容量为
V
V
V 的背包，每种物品都有无限件可用。放入第
i
i
i 种物品的费用是
C
i
C_i
Ci，价值是
W
i
W_i
Wi。求解：将哪些物品装入背包，可使这些物品耗费的费用总和不超过背包容量，且价值总和最大。
基本思路
与01背包问题相似，唯一不同是每种物品有无限件。即从物品角度，相关策略从取或不取两种，变为取 0 件、取 1 件、取 2 件…直到取
⌊
V
/
C
i
⌋
\lfloor V/C_i \rfloor
⌊V/Ci⌋ 件。
按01背包思路，令
F
[
i
,
v
]
F[i, v]
F[i,v] 表示前
i
i
i 种物品正好放入一个容量为
v
v
v 的背包的最大价值。状态转移方程为：
F
[
i
,
v
]
=
m
a
x
{
F
[
i
−
1
,
v
−
k
C
i
]
+
k
W
i
∣
0
≤
k
C
i
≤
v
}
F[i, v] = max\{F[i-1,v-kC_i]+kW_i|0 \leq kC_i \leq v\}
F[i,v]=max{F[i−1,v−kCi]+kWi∣0≤kCi≤v}
和01一样共有
O
(
V
N
)
O(VN)
O(VN) 个状态需求解，但解每个状态的时间不是常数了，解状态
F
[
i
,
v
]
F[i, v]
F[i,v] 的时间是
O
(
v
/
C
i
)
O(v/C_i)
O(v/Ci) ，总复杂度为
O
(
N
V
∑
V
/
C
i
)
O(NV\sum V/C_i)
O(NV∑V/Ci) 。
优化
-
O
(
N
2
)
O(N^2)
O(N2) 优化
若物品
i
i
i 、
j
j
j 满足
C
i
≤
C
j
C_i \leq C_j
Ci≤Cj 且
W
i
≥
W
j
W_i \geq W_j
Wi≥Wj 可将物品j直接去除。
-
O
(
V
+
N
)
O(V + N)
O(V+N)优化
先将费用大于
V
V
V 的物品去除，然后类似计数排序，计算出费用相同的物品中价值最高的物品。
转化为01背包问题求解
简单做法
可用把第
i
i
i 种物品转化为
⌊
V
/
C
i
⌋
\lfloor V/C_i \rfloor
⌊V/Ci⌋ 件费用及价值都不变的物品，然后求解01背包。
更高效转化
把第
i
i
i 种物品拆成费用为
C
i
2
k
C_i2^k
Ci2k 、价值为
W
i
2
k
W_i2^k
Wi2k 的若干件物品，其中
k
k
k 是满足
C
i
2
k
≤
V
C_i2^k \leq V
Ci2k≤V 的非负整数，复杂度
O
(
log
⌊
V
/
C
i
⌋
)
O(\log \lfloor V/C_i \rfloor)
O(log⌊V/Ci⌋) 。
模板
typedef long long ll;
void CompletePack(ll F[], ll C, ll W, ll Cap)
{
for(int v = C; v <= Cap; v++)
F[v] = max(F[v], F[v - C] + W);
}
ll Solve(const ll C[],const ll W[], const ll N, const ll Cap)
{
ll F[Cap+1];
memset(F,0,sizeof(F));
//优化
bool Use[N+1];
// O(N^2)优化
// memset(Use,true,sizeof(Use));
// for(int i = 1; i <= N; i++)
// for(int k = i+1; k <= N; k++)
// if(C[i] <= C[k] && W[i] >= W[k])
// Use[k] = false;
// O(V + N)优化
memset(Use, false, sizeof(Use));
map<ll, int> Cnt;
for(int i = 1; i <= N; i++)
{
if(C[i] > Cap)
continue;
if(Cnt[C[i]] == 0)
Cnt[C[i]] = i, Use[i] = true;
else if(W[i] > W[Cnt[C[i]]])
Use[Cnt[C[i]]] = false, Use[i] = true, Cnt[C[i]] = i;
}
for(int i=1; i <= N; i++)
if(Use[i]) //优化
CompletePack(F, C[i], W[i], Cap);
return F[Cap];
}
