小赖子的英国生活和资讯

ACM题解 – 经典0/1背包问题

JustYY.com 小赖子的英国生活和资讯
阅读 桌面完整版
acm-association-computing-machinery ACM题解 - 经典0/1背包问题 ACM题解 I.T. 数据结构与算法 程序设计

acm-association-computing-machinery

0/1背包问题是非常经典的算法问题. 要求是: 给定 n 个物件, 每个物件的重量(或体积)是 A[i] 那么请问一个最多装重(或体积) m 的背包最多可以装下多少这些物件.

如果用数学表示这个问题:

max(sum(j[i] * A[i]))
subject to: j[i] = {0, 1} and sum(j[i] * A[i]) <= m
where 0 =< i < n

j[i] 就是控制是否装下第 i 个 物件 的变量(0或者1)

回溯算法

把整个搜索空间从第一个物件开始当成树根, 那么这是一棵二叉树, 每层的节点就能对应到每个物品, 两个分叉分别代表是否把当前节点(物品)装入背包中.

不难想像, 时间复杂度为 O(2^n). 如果当前背包并不能装下当前物件, 那么我们需要继续尝试下一个物品, 直到所有物品尝试完并回溯. 

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

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
     
    int backPack(int m, vector<int> &A) {
        pack(0, m, A);
        return curMax;
    }
 
    void pack(int n, int weight, vector<int> &A) {
        int sz = A.size();
        int m = 0;
        for (int i = n; i < sz; i ++) {
            pack(n + 1, weight, A);  // 不放
            if (weight >= A[i]) {   // 可以放
                m += A[i];
                if (m > curMax) {
                    curMax = m;
                }
                weight -= A[i];
                pack(n + 1, weight, A);  // 放
            } 
        }
    }
    
private:
    int curMax = 0;
};
class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
     
    int backPack(int m, vector<int> &A) {
        pack(0, m, A);
        return curMax;
    }

    void pack(int n, int weight, vector<int> &A) {
        int sz = A.size();
        int m = 0;
        for (int i = n; i < sz; i ++) {
            pack(n + 1, weight, A);  // 不放
            if (weight >= A[i]) {   // 可以放
                m += A[i];
                if (m > curMax) {
                    curMax = m;
                }
                weight -= A[i];
                pack(n + 1, weight, A);  // 放
            } 
        }
    }
    
private:
    int curMax = 0;
};

这个算法的问题就是慢. 特别是物品数量多的时候, 整个搜索空间就变得巨大.

动态规化

如果我们用 dp[i][j] 来表示是否可以用最多 前 i 件物品来装最多重量(或者体积) 为 j . 那么: 

1

dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]];
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]];

我们可以反过来理解:

动态规化的优点就是可以把中间结果给缓存起来, 这样就不会像递规回溯一样有些结果(中间节点)会重复计算. 

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

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
     
    int backPack(int m, vector<int> &A) {
            int size = A.size();
            vector< vector<bool> > dp(size + 1, vector<bool>(m + 1, false));
            for (int i = 0; i < size + 1; ++ i) {
                dp[i][0] = true;
            }
            for(int i = 1; i < A.size() + 1; i++) {
                for(int j = 1; j < m + 1; j++) {
                    if(j < A[i - 1]) {  // 装不下了
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]];
                    }
                }
            }
            for (int i = m; i >= 0; i--) { // 反过来从大到小检查能装下的最大重量
                if (dp[size][i]) {
                    return i;
                }
            }
            return 0;
    }
};
class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
     
    int backPack(int m, vector<int> &A) {
            int size = A.size();
            vector< vector<bool> > dp(size + 1, vector<bool>(m + 1, false));
            for (int i = 0; i < size + 1; ++ i) {
                dp[i][0] = true;
            }
            for(int i = 1; i < A.size() + 1; i++) {
                for(int j = 1; j < m + 1; j++) {
                    if(j < A[i - 1]) {  // 装不下了
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]];
                    }
                }
            }
            for (int i = m; i >= 0; i--) { // 反过来从大到小检查能装下的最大重量
                if (dp[size][i]) {
                    return i;
                }
            }
            return 0;
    }
};

时间复杂度和空间复杂度都是 O(nm). 最后面我们只要反过来检查 dp[A.size()][j] 为 true 的第一个下标 j 就是当前背包能装下的最大重量.

DP 内存优化

上面的DP公式我们不难发现, 在计算 dp[i] 的时候只依赖于 dp[i-1], 这样我们就可以只用一维来存取 dp[i-1] 的情况. 这样, 空间复杂度从 O(mn) 就降到了 O(m).

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:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
     
    int backPack(int m, vector<int> &A) {
            int size = A.size();
            vector<bool> dp(m + 1, false);
            dp[0] = true;
            for (int i = 1; i < A.size() + 1; i++) {
                for (int j = m; j >= 1; --j) { // // 内循环需要从 m 到 1 的检查
                    if(j >= A[i - 1]) {
                        dp[j] = dp[j] || dp[j - A[i - 1]];
                    }
                }
            }
            for (int i = m; i >= 0; i--) {
                if (dp[i]) {
                    return i;
                }
            }
            return 0;
    }
};
class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
     
    int backPack(int m, vector<int> &A) {
            int size = A.size();
            vector<bool> dp(m + 1, false);
            dp[0] = true;
            for (int i = 1; i < A.size() + 1; i++) {
                for (int j = m; j >= 1; --j) { // // 内循环需要从 m 到 1 的检查
                    if(j >= A[i - 1]) {
                        dp[j] = dp[j] || dp[j - A[i - 1]];
                    }
                }
            }
            for (int i = m; i >= 0; i--) {
                if (dp[i]) {
                    return i;
                }
            }
            return 0;
    }
};

英文: Algorithms Series: 0/1 BackPack – Dynamic Programming and BackTracking

强烈推荐

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版

相关文章：

  1. Javascript 中 sleep 函数实现 阅读 桌面完整版 Javascript 中并没有 built-in 的 sleep 函数支持, 在 async/await/Promise 的支持之前, 我们可以用 busy-waiting 的方式来模拟: 1...
  2. [活动] 晒晒你的18岁 What did you look like when you were 18? 阅读 桌面完整版 快2018年了, 最近朋友圈在晒18岁, 你的18岁是怎么样的呢? 我们就来接个力, 晒晒你的18岁. It is almost 2018, so what did you...
  3. 拔牙后的注意事项(图, 慎入) Care of Mouth after Extraction 阅读 桌面完整版 昨天又拔了两颗牙, 初步定在5月4号装牙套. 这是牙医诊所给的术后注意事项: 拔完后需要等3-4小时麻醉失效后才能吃喝. 稍微流点血是很正常的. 但是请不要漱口吐出, 因为这会加速流血. 你只要轻轻的含着口水并咽下即可. 如果一直流血, 请拿着纱布(并不是纸巾)放在拔牙处20分钟. 24小时内请不要运动, 术后几小时内回家静静坐着. 12小时内不要吸烟,...
  4. 按揭贷款(房贷,车贷) 每月还贷计算器 阅读 桌面完整版 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的....
  5. 把年假分成几周请完 – 工作不是全部 阅读 桌面完整版 我的工作合同里写着 一年享有 25年工作日 带薪假期 这是比较好的福利之一. 搬家的时候请了三天 还有就是零零散散请了几天 比如 看GP 等等. 每年假期可以有 5天能移到 下一年使用...
  6. 试用 Linkedin (领英) 高级帐号 (Premium) 阅读 桌面完整版 Linkedin (领英) 算是比较靠谱的职业社交网站, 在上面有很多猎头, 很多知名公司的HR 无时无刻在招人. 特别领英在被微软收购之后, 名气就变得大了许多. 领英是免费使用的, 但也有付费用户, 有给猎头的, 也有给想找工作的. 价格并不便宜,...
  7. C编程练习题: 翻转整数位 阅读 桌面完整版 题意: 给定两个整数, 计算从一个整数需要翻转几个位才能到另一个整数. 比如: 给定29 二进制为11101 和 15, 二进制是01111, 则答案是2次. 这题的关键就是用 XOR 异或来获得两个整数不同位....
  8. 《Steem 指南》之 justyy 在线工具与 API 系列 – Discord 机器人 阅读 桌面完整版 Discord 聊天频道 Discord 原本是给游戏设计的, 但由于其功能多, 接口开放能力强, 使用的用户越来越多. 我们CN区也有一个Discord 频道, 加入地址为: https://discord.gg/7ctT3Xt 在网页里就可以加入 cnsteem...
Exit mobile version