stone

背包小练
相关资料:背包九讲https://www.kancloud.cn/kancloud/pack/70134内容较多,...
扫描右侧二维码阅读全文
03
2019/01

背包小练

相关资料:

背包九讲
https://www.kancloud.cn/kancloud/pack/70134

内容较多,分两周做题目

题目来源
https://www.cnblogs.com/mhpp/p/6672094.html

第一周 0-1背包 完全背包

  1. easy hdu 2602 Bone Collector http://acm.hdu.edu.cn/showproblem.php?pid=2602
  2. easy hdu 2546 饭卡 http://acm.hdu.edu.cn/showproblem.php?pid=2546
  3. medium hdu 2955 Robberies http://acm.hdu.edu.cn/showproblem.php?pid=2955
  4. medium hdu 1059 Dividing http://acm.hdu.edu.cn/showproblem.php?pid=1059
  5. hard poj 3260 The Fewest Coins http://poj.org/problem?id=3260

第二周 完全背包 分组背包

  1. http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4439 zju 4439 Crazy Shopping
  2. http://poj.org/problem?id=3260 poj 3260 The Fewest Coins
  3. http://poj.org/problem?id=1787 poj 1787 Charlie's Change
  4. http://poj.org/problem?id=1276 poj 1276 Cash Machine
  5. http://acm.hdu.edu.cn/showproblem.php?pid=3535 hdu 3535 AreYouBusy

相关实现代码: https://github.com/dong100136/interviews/tree/master/leetcode


01背包

背包问题中,物品有重量和价值,要求在给定的容量中,装下价值最大的物品。
同时规定,物品只能放一次。

经典的背包问题,一个简单的空间优化是用一个一维数组来表示当前重量下的状态,
每次从重量较大的一边开始更新,覆盖之前的结果,从而将空间复杂度从O(NV)优化为O(V)

该问题的时间复杂度为O(NV)

相关题目:

1. easy hdu 2602 Bone Collector 简单01背包

2. easy hdu 2546 饭卡


分两种情况: 如果小于5元,什么都不可以买,如果大于5元,则先用最后剩下来的钱来买最贵的菜,然后,就是在总钱数上做01背包问题了

3. medium hdu 2955 Robberies


抢劫银行,对于每个银行有一个钱数和被抓的概率。
简单看来,受限制的是概率,要求被抓的概率不大于某个数,但是概率为浮点数,不好作为数组的下标,所以将钱数作为重量来看。所以这就是一个无线容量的背包,尽可能装下超过某个价值的东西。

值得注意的是,被抓的概率不能直接使用,要用不被抓的概率,概率之间要用乘法来处理。

最后,只要选择不被抓的情况下能拿最多钱的情况就可以了。

4. poj 1276 Cash Machine


提款机中有个一定数量的纸币,给出一个需要提款的金额,输出能够提取出来最接近的金额,很基本的多重背包问题,不深究了

5. poj 1787 Charlie's Change 路径记录


买咖啡,给定咖啡的金额,然后给出1,5,10,25面值的硬币,尽可能给出最多硬币,并刚好可以付咖啡

使用另外的一个数组来记录状态

完全背包和多重背包

0. medium poj 3260 The Fewest Coins

有多个不同价值的硬币,要用最小的硬币数进行交易。
完全背包+多重背包+二进制优化,比较综合

http://www.hankcs.com/program/algorithm/poj-3260-the-fewest-coins.html

二进制优化是通过将一个数查分为多个2的倍数的物品,将问题转换为01背包问题

搜索的上界的确定用鸽笼原理,为max_coins*max_coins+T,具体原理不懂

放两个模板代码,注意循环上面的细节。
// 多重背包
int[] dp1 = new int[max_w + 1];
for (int i = 0; i <= max_w; i++) {
    dp1[i] = 1000000;
}

dp1[0] = 0;

for (int i = 0; i < N; i++) {
    for (int k = 1; c[i] > 0; k <<= 1) {
        k = Math.min(k, c[i]);
        int nv = k * v[i];
        for (int j = max_w; j >= nv; j--) {
            dp1[j] = Math.min(dp1[j], dp1[j - nv] + k);
        }
        c[i] -= k;
    }
}

//完全背包
max_w = max_coins * max_coins;
int[] dp2 = new int[max_w + 1];
for (int i = 0; i <= max_w; i++) {
    dp2[i] = 1000000;
}
dp2[0] = 0;

for (int i = 0; i < N; i++) {
    for (int j = v[i]; j <= max_w; j++) {
        dp2[j] = Math.min(dp2[j], dp2[j - v[i]] + 1);
    }
}  

分组背包

0. hdu 3535 AreYouBusy


有n组任务和T分钟,任务组的类型有三种,0代表必须选择其中一个任务,1代表最多选择其中一个任务,2代表可以选任意多的

对于每个任务,完成任务要用t分钟,可以获取c的快乐值

求可以获得的最大快乐值

dp[i][j] 代表第i组商品,重量为j的情况下,有三种不同的类型:

a. 必须选择一个
    dp[i][j] = max(dp[i][j],dp[i-1][j-w[k]]+v[k],dp[i][j-w[k]]+v[k])
    
    对于第i组物品,现将当前的状态设置为负无穷,这样对于这种的物品,则必然会有一个被选择
    
b. 最多选择一个
    dp[i][j] = max(dp[i][j],dp[i-1][j-w[k]]+v[k])
    
    要么不选,要么从上一组的状态加上本组的一个任务
    
c. 任意选择
    dp[i][j] = max(dp[i][j],dp[i][j-w[k]]+v[k])
    
    普通的01背包
    
因为当前的状态最多和前一组的状态相关,所以可以用滚动数组的方法,优化空间

二维费用背包 拓扑排序

拓扑排序资料: https://songlee24.github.io/2015/05/07/topological-sorting/

0. zju 4439 Crazy Shopping 没有ac

有一个N个城镇和M条路,每个城镇唯一的纪念品,并有一个重量Tw和Tv,当背包有重量n时,走k长度的路会消耗k个能量,求在获得最大价值的同时消耗最小的能量

拓扑排序,统计每一个点入度,
每次从队列中取一个点,然后和其连接的点的度减一,将入度为0的点放入队列中,
从而确定点的遍历顺序。

在给出遍历顺序的情况下,依次枚举做dp




Last modification:January 3rd, 2019 at 10:58 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment