贪心-部分背包

  |  

摘要: 部分背包问题

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


01 背包和完全背包是动态规划中很基础并且很重要的一类问题。

在 01 背包的基础上,对于每个物品 i,如果可以拿走其一部分,而不是只能做二元选择,这种问题称为部分背包问题。该问题可以通过贪心解决。

本文首先回顾一下 01 背包问题的描述及其动态规划解法,然后给出部分背包问题的描述以及贪心算法,之后通过模板题给出代码模板。最后我们讨论硬币找零问题。


01背包回顾 (0-1 Knapsack Problem)

有 n 种物品,物品 i 的体积为 $v_{i}$, 价值为 $w_{i}$, 有一个体积限制 V。如何选择物品使得总体积不超过 V,并使得总价值最大。

算法 : 动态规划

1
dp[i][j] := 已经考虑了 [0..i-1]  前 i 个物品,占用了 j 空间,所能取得的最大价值。

转移方式有两种,一种是放入,一种是不放入。 如果放,则前 i - 1 个只能占 j - v[i] 空间,如果不放,则前 i - 1 个物品还是占了 j 空间

1
2
dp[i][j] = dp[i - 1][j] 当前物品不选
dp[i - 1][j - v[i]] + w[i] 当前物品选,j - v[i] 要大于等于 0

部分背包问题 (0-1 Fractional Knapsack Problem)

基础设定与 01 背包一样。但是对于每个物品 i,可以拿走其一部分,而不是只能做二元选择

部分背包问题的典型描述

给定一个最大载重量为 M 的卡车和 N 种食品。已知第 i 种食品的最多拥有 V[i] 公斤,其商品价值为 W[i] 元/公斤,确定一个装货方案,使得装入卡车中的所有物品总价值最大。

注意以上描述中的 W[i] 相当于性价比

算法: 贪心

求每个物品的性价比 $w[i]/v[i]$,(有的问题会直接给出例如”单位体积的价值为…”这种描述)。

尽可能先拿性价比高的物品,当该物品拿完且背包尚未装满,则尽量多那性价比次高的,以此类推,直到背包装满

将 $w[i]/v[i]$ 排序,可以 $O(N\log N)$ 实现贪心算法。

$O(N)$ 的贪心算法

Ref:《算法导论》习题 16-2-6

使用线性算法找出 $w[i]/v[i]$ 的中位数 m: $O(N)$, Ref 《算法导论》9-2。

将物体分成三个集合:$O(N)$

  • $G = \{i : w[i]/v[i] > m\}$
  • $E = \{i : w[i]/v[i] = m\}$
  • $L = \{i : w[i]/v[i] < m\}$

计算 $V_{G} = \Sigma(v[i]), i \in G; V_{E} = \Sigma(v[i]), i \in E$

  • 如果 $W_{G} > W$,则不在 G 中取出任何物体,而是继续递归分解 G
  • 如果 $W_{G} <= W$,取出 G 中所有物体,并尽可能多得取出 E 中物体
  • 如果 $W_{G} + W_{E} >= W$,也就是说背包已经放满,则问题解决
  • 否则如果尚未放满,则继续在 L 上递归调用查找 $W – W_{G} - W_{E}$ 的方案

以上所有调用都在线性时间内完成,每次递归调用都能减少一半的数据规模,因此递归式为:

由主定理: $T(n) = O(n)$。

部分背包问题模板题

有 N 堆金币,第 i 堆金币的总重量和总价值分别为 m[i] 和 v[i]。有一个承重为 T 的背包,想装走尽可能多价值的金币,所有金币可以随意分割,分割完的金币重量价值比不变,问最多拿走多少价值的金币。

1
2
3
4
5
6
输入格式:
第一行两个整数 N, T。
接下来 N 行,每行两个整数 m[i], v[i]

输出格式:
一个实数表示答案,输出两位小数

输入
4 50
10 60
20 100
30 120
15 45
输出
240.00

代码 (C++,模板)

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
struct Item
{
int v, w; // v: 体积, w: 价值
Item(int v, int w):v(v),w(w){}
};

struct Cmp
{
bool operator()(const Item& i1, const Item& i2) const
{
return (double)i1.w / i1.v > (double)i2.w / i2.v;
}
};

int main()
{
int N, T;
cin >> N >> T;
vector<Item> items(N, Item(-1, -1));
for(int i = 0; i < N; ++i)
{
cin >> items[i].v;
cin >> items[i].w;
}
sort(items.begin(), items.end(), Cmp());
double ans = 0.0;
for(const Item &item: items)
{
if(item.v >= T)
{
ans += (double)item.w / item.v * T;
break;
}
else
{
ans += (double)item.w;
T -= item.v;
}
}
cout.precision(2);
cout.setf(ios::fixed);
cout << ans << endl;
}

01背包和部分背包的对比(动态规划和贪心的对比)

贪心和动态规划

最优解问题大部分都可以拆分成一个个的子问题,解空间的遍历可以视为树的遍历

这种对解空间对应的树上遍历一遍求出最优解的方法是搜索,搜索的本质是树的遍历

搜索过程中可能遇到重复子问题,此时将子问题的结果保存下来形成动态规划,本质还是树的遍历,只是不会重复搜索了

贪心算法是在子问题对应的树上进行搜索过程中的一种很强的剪枝

联系

贪心和动态规划算法都要求问题都具有最有子结构:组成最优解的每一个子问题的解,对于这个子问题本身肯定也是最优的

区别

  • 动态规划方法代表了这一类最优解问题的一般解法:自底向上构造子问题的解,对每一个子树的根,求出该子树每一个叶子的值,并且以其中的最优值作为自身的值,其它的值舍弃。(当然动态规划不止可以解决最优解问题)
  • 贪心是动态规划一个特例:每一个子树根的值不取决子树的叶子的值,而只取决于当前节点的一些特性,因此贪心对解空间树的遍历从叶子开始构建各个子树的解雇,而只需要从根开始,依据当前节点的特性,选择最优的路,一直走到某个叶子就可以了。

装载问题

你有一些苹果和一个可以承载 5000 单位重量的篮子。

给定一个整数数组 weight ,其中 weight[i] 是第 i 个苹果的重量,返回 你可以放入篮子的最大苹果数量 。

示例 1:
输入:weight = [100,200,150,1000]
输出:4
解释:所有 4 个苹果都可以装进去,因为它们的重量之和为 1450。

示例 2:
输入:weight = [900,950,800,1000,700,800]
输出:5
解释:6 个苹果的总重量超过了 5000,所以我们只能从中任选 5 个。

提示:

1
2
1 <= weight.length <= 1e3
1 <= weight[i] <= 1e3

算法:贪心

有 n 个物品,第 i 个物体的重量为 w[i] > 0。选择尽量多的物品,使得总重量不超过 C。

贪心思路:

1
装重的物体没有装轻的物体划算

注意两点

  • 考虑的是物品最大数量而不是最大重量,如果最大重量需要考虑DP。
  • 如果物品还有一个价值字段,且可以一单位重量一单位重量地取,求总重量不超过 C 的最大价值,就是部分背包问题。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maxNumberOfApples(vector<int>& arr) {
int V = 5000;
sort(arr.begin(), arr.end());
int cnt = 0;
for(int i: arr)
{
if(V < i)
break;
++cnt;
V -= i;
}
return cnt;
}
};

硬币找零问题

518. 零钱兑换 II

问题

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

动态规划

完全背包,无价值,恰好取得背包容量

1
2
3
dp[j] := 容量为 j 的方案数
dp[0] = 1
dp[j] = sum(dp[j - v[i]]) j - v[i] >= 0
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
class Solution {
public:
int change(int amount, vector<int>& coins) {
// if(amount == 0) return 1;
int N = coins.size();

vector<int> dp(amount + 1, INT_MIN);
dp[0] = 0;
vector<int> g(amount + 1, 0);
g[0] = 1;

for(int i = 0; i < N; ++i)
for(int j = coins[i]; j <= amount; ++j)
{
int s = 0;
int t = max(dp[j], dp[j - coins[i]]);
if(dp[j] == t) s += g[j];
if(dp[j - coins[i]] == t) s += g[j - coins[i]];
g[j] = s;
dp[j] = t;
}
if(g[amount] == INT_MIN) return 0;
return g[amount];
}
};

可以优化为贪心情况

  • 硬币找零问题中,有一些硬币组合可以采用贪心策略,即有限选面值大的,面值大的选不了,再考虑面值小的,例如以下两种:
1
2
1,5,10,50 
1,5,10,20,50,100
  • 但贪心可能会有错误,例如这种硬币组合 1,5,7,10,如果要找 14 块钱,按照贪心会选 10, 1, 1, 1, 1 共五枚硬币。

  • 当硬币组合为 $c^{0}, c^{1}, …, c^{n}$ 时,可贪

  • 当硬币组合为斐波那契数列时候,可贪 (见后面的问题)

  • 有算法可以在 O(n^3) 的时间内判断组合是否可以用贪心。A Polynomial-time Algorithm for the Change-Making Problem

  • 算法导论中关于硬币找零问题的习题,以上一些结论的证明在里面

硬币找零问题


1414. 和为 K 的最少斐波那契数字数目

  • 当硬币组合为斐波那契数列时候,可贪

斐波那契面值可贪性证明

官解

代码

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
class Solution {
public:
int findMinFibonacciNumbers(int k) {
// 预处理所有 f <= k
vector<int> f{1, 2};
int prev = 1;
while(f.back() + prev <= k)
{
int cur = f.back();
f.push_back(cur + prev);
prev = cur;
}
int ans = 0;
int m = f.size();
int it = m - 1;
while(k > 0)
{
while(it >= 0 && f[it] > k)
--it;
if(it < 0)
return -1;
k -= f[it];
++ans;
}
return ans;
}
};

最少硬币组合出 1~m 的所有面值

有 n 种不同面值的硬币,每种硬币有无限多个。选出尽量少的硬币,但是要能组合出 1 到 m 之间的任意值。

这个问题与背包关系不大,但是也是硬币找零的一个经典问题。

首先判断有无解,如果最小面额硬币大于1则无解,因为搭配不出1。如果有1则有解,因为所有面额都可以由1堆积出来。

当前已经选的硬币的面值和为 sum(初始时 sum = 1)。此时 1~sum 均可以组合出。sum + 1 此时尚未组合出,需要增加一枚,如果增加的是 x,则 sum + 1 ~ sum + x 就都组合出来了。为了覆盖到尚未覆盖到的 sum + 1 这一面值,增加<= sum + 1 的硬币中最大的哪一个是最好的。

这个贪心的思路与区间覆盖问题有点像。

类似的问题: 330. 按要求补齐数组

问题

给定一个已排序的正整数数组 nums,和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中,使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。

分析

记 miss 是缺失数字中最小的,[1, miss) 已经被覆盖

为了覆盖 miss,必须加入某个 x <= miss 的数字,此时 [x, miss + x) 已经覆盖

因此希望选择尽可能大的 x,这样的话增加一个数之后,可以确定覆盖的范围可以达到最大。因此取 x = miss

这个贪心的思路与区间覆盖问题有点像。

1
2
3
4
5
6
7
8
9
10
初始化 miss = 0, i = 0, cnt = 0
迭代 miss 直到 miss > n:
检查 nums,若 nums[i] <= miss:
miss += nums[i]
++i
否则:
加入 miss, miss *= 2
++cnt;

贪心地取补充的数为 x = miss,有点区间覆盖问题的意思

代码

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
class Solution {
public:
int minPatches(vector<int>& nums, int n) {
int m = nums.size();
using ll = long long;
ll miss = 1;
int i = 0;
int ans = 0;
while(miss <= n)
{
if(i < m && nums[i] <= miss)
{
// 取到 [1, miss) 时尚未用到 nums[i]
miss += nums[i];
++i;
}
else
{
miss *= 2;
++ans;
}
}
return ans;
}
};

Share