相关资料:
背包九讲
https://www.kancloud.cn/kancloud/pack/70134
内容较多,分两周做题目
题目来源
https://www.cnblogs.com/mhpp/p/6672094.html
第一周 0-1背包 完全背包
- easy hdu 2602 Bone Collector http://acm.hdu.edu.cn/showproblem.php?pid=2602
- easy hdu 2546 饭卡 http://acm.hdu.edu.cn/showproblem.php?pid=2546
- medium hdu 2955 Robberies http://acm.hdu.edu.cn/showproblem.php?pid=2955
- medium hdu 1059 Dividing http://acm.hdu.edu.cn/showproblem.php?pid=1059
- hard poj 3260 The Fewest Coins http://poj.org/problem?id=3260
第二周 完全背包 分组背包
- http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4439 zju 4439 Crazy Shopping
- http://poj.org/problem?id=3260 poj 3260 The Fewest Coins
- http://poj.org/problem?id=1787 poj 1787 Charlie's Change
- http://poj.org/problem?id=1276 poj 1276 Cash Machine
- 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