算法基础算法

贪心-部分背包

字数统计: 3.3k字   |   阅读时长: 13分
, ,

摘要: 部分背包问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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