相关资料：
背包九讲
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
