LeetCode-Day51

背包问题

0/1背包问题

有 $N$ 件物品和一个容量为 $V$ 的背包。第iii件物品的费用是 $w[i]$ ，价值是 $v[i]$ ，求将哪些物品装入背包可使价值总和最大。

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即 $f[i][j]$ 表示前 $i$ 件物品恰放入一个容量为 $j$ 的背包可以获得的最大价值。则其状态转移方程便是

f[i][j]= max(f[i-1][j], f[i-1][j-w[i]]+v[i])

优化空间复杂度之后的代码：

1
2
3

for (int i = 0; i < n; i++)
    for (int j = V; j >= w[i]; j--)
        f[j] = max(f[j], f[j - w[i]] + v[i]);

初始化的细节问题

有的题目要求"恰好装满背包"时的最优解，有的题目则并没有要求必须把背包装满。这两种问法的区别是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了 $f[0]$ 为 $0$ 其它 $f[1...V]$ 均设为 $−∞$ ，这样就可以保证最终得到的 $f[N]$ 是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 $f[0...V]$ 全部设为 $0$ 。
为什么呢？可以这样理解：初始化的 $f$ 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 $0$ 的背包可能被价值为 $0$ 的 $nothing$ “恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是 $−∞$ 了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 $0$ ，所以初始时状态的值也就全部为 $0$ 了。

版权声明：本文为CSDN博主「良月澪二」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/yandaoqiusheng/article/details/84782655

例题：

HDU 3466 Proud Merchants

题目大意：有n件商品，每件商品的价格是pi，每件商品只有在你的钱大于等于qi时才可以买入，每件商品在你心目中都有价值vi。现在你有m元钱，如何实现使买到的商品价值最大。

思路：如果没有q的存在，那就是一个典型的0/1背包问题。那么，在0/1背包的基础上考虑q，无疑是跟顺序有关。比方说有A、B、C三件物品如下，一旦确定要买之后，一定是先买A商品，再买C商品，那接下来是不是就不需要考虑顺序，只需要使用以上的0/1背包算法直接来。这就是我们的思路，先把顺序给考虑了，在套用以上0/1背包算法。

3 10
5 5 5 ----A商品
3 3 6   ----B商品
2 3 3   ----C商品

其实，就是让C商品的q不等于p，其他都相同，这时，你就会发现如果要买C商品的话，肯定得先买C商品，因为买C商品的代价最大。所以，我们可以按照qi-pi的顺序来确定大顺序。这里我们还可以用更严谨的方式来证明一下，比如A:p1 q1, B:p2 q2，然后，假设单独买A或者B的话，都是可以买到的。这时，若先买A，则你至少需要p1+q2的钱；若先买B，则至少需要p2+q1的钱。那肯定是花最少的钱咯，所以如果先买A再买B，那么p1+q2<p2+q1，转换一下，就是q1-p1>q2-p2，也就是说qi-pi大的先买。**这里还得注意一点就是，排序的时候，得按照qi-pi从小到大排序，因为你买第n件商品的时候，是在比较你是否要先买第n件商品。**打个比方让大家更好地理解，比如说f(3, 10)，是不是max(f(2, 10-p3)+v3, f(2, 10))，你会发现这个第一种情况f(2,10-p3)+v3中，是先买了第三件商品，也就是说排在后面的商品会先买。好的，排好序之后，就把问题就转换为不需要考虑顺序的问题了，那就是上面我们已经解决0/1背包问题了。这样，问题圆满解决了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
const int MAXM = 5005;
struct node {
    int p, q, v;
};
bool cmp(node a, node b) {
    return (a. q - a.p) < (b.q - b.p); 
}
node pro[MAXN];
int dp[MAXM];
int n, m;
void solve() {
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < n; i++) {
        for(int j = m; j >= pro[i].q; j--) {
            dp[j] = max(dp[j], dp[j - pro[i].p] + pro[i].v);
        }
    }
    printf("%d\n", dp[m]);
}

int main() {
    while(scanf("%d%d", &n, &m) != EOF) {
        for(int i = 0; i < n; i++) {
            scanf("%d%d%d", &pro[i].p, &pro[i].q, &pro[i].v);
        }
        sort(pro, pro + n, cmp);
        solve();
    }
}

完全背包问题

有 $N$ 种物品和一个容量为 $V$ 的背包，每种物品都有无限件可用。第 $i$ 种物品的费用是 $w[i]$ ，价值是 $v[i]$ 。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

优化复杂度之后的代码：

1
2
3

for (int i = 1; i <= n; i++)
    for (int j = w[i]; j <= V; j++)
        f[j] = max(f[j], f[j - w[i]] + v[i]);

例题：

Luogu 1853 投资的最大效益

约翰先生获得了一大笔遗产，他暂时还用不上这一笔钱，他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券，每一种债券都能在固定的投资后，提供稳定的年利息。当然，每一种债券的投资额是不同的，一般来说，投资越大，收益也越大，而且，每一年还可以根据资金总额的增加，更换收益更大的债券。

描述：

例如：有如下两种不同的债券：①投资额4000，年利息4000，年利息400；②投资额3000，年利息3000，年利息250。初始时，有10000的总资产，可以投资两份债券①债券，一年获得10000的总资产，可以投资两份债券①债券，一年获得800的利息；而投资一份债券①和两份债券②，一年可获得900的利息，两年后，可获得900的利息，两年后，可获得1800的利息；而所有的资产达到11800，然后将卖掉一份债券②，换购债券①，年利息可达到11800，然后将卖掉一份债券②，换购债券①，年利息可达到1050；第三年后，总资产达到12850，可以购买三份债券①，年利息可达到12850，可以购买三份债券①，年利息可达到1200，第四年后，总资产可达到$14050。

现给定若干种债券、最初的总资产，帮助约翰先生计算，经过n年的投资，总资产的最大值。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 13;
const int MAXM = 10000;
int s, n, d;
int w[MAXN], v[MAXN];
int dp[MAXM];   
int solve(int s) {
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < d; i++) {
        for(int j = int(w[i]/1000); j <= int(s/1000); j++) {
            dp[j] = max(dp[j], dp[j-(w[i]/1000)] + v[i]);
        }
    }
    return s + dp[s/1000];
}

int main() {
    scanf("%d%d%d", &s, &n, &d);
    for(int i = 0; i < d; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    for(int i = 0; i < n; i++) {
        s = solve(s);
    }
    printf("%d\n", s);
}

多重背包问题

有 $N$ 种物品和一个容量为 $V$ 的背包。第 $i$ 种物品最多有 $p[i]$ 件可用，每件费用是 $w[i]$ ，价值是 $v[i]$ 。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

for (int i = 1; i <= n; i++) {
    int num = min(p[i], V / w[i]);
    for (int k = 1; num > 0; k <<= 1) {
        if (k > num) k = num;
        num -= k;
        for (int j = V; j >= w[i] * k; j--)
            f[j] = max(f[j], f[j - w[i] * k] + v[i] * k);
    }
}

混合背包问题

01背包与完全背包的混合

考虑到在01背包和完全背包中给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是 $O(VN)$

p[i]:每个物品的件数，0代表无穷个
for (int i = 1; i <= n; i++)
    if (p[i] == 0)
        for (int j = w[i]; j <= V; j++)
            f[j] = max(f[j], f[j - w[i]] + v[i]);
    else
    for (int k = 1; k <= p[i]; k++)
        for (int j = V; j >= w[i]; j--)
            f[j] = max(f[j], f[j - w[i]] + v[i]);

例题：

HDU 3535 AreYouBusy

https://www.cnblogs.com/coredux/archive/2012/07/26/2610868.html

这是一道综合性的背包问题。题目给出了多组工作，每组工作的选择规则不同，有些组至少要选一项，有些组最多选一项，有些组任意选。

这道题花了很长时间，需要深入理解状态转移才能够明白。数组dp[i][j],表示第i组，时间剩余为j时的快乐值。每得到一组工作就进行一次DP，所以dp[i]为第i组的结果。下面对三种情况进行讨论。

第一类，至少选一项，即必须要选，那么在开始时，对于这一组的dp的初值，应该全部赋为负无穷，这样才能保证不会出现都不选的情况。状态转移方程为dp[i][k]=max{ dp[i][k],dp[i-1][k-cost[j]]+val[k],dp[i][k-cost[j]]+val[j] }。dp[i][k]是不选择当前工作；dp[i-1][k-cost[j]]+val[k]是选择当前工作，但是是第一次在本组中选，由于开始将该组dp赋为了负无穷，所以第一次取时，必须由上一组的结果推知，这样才能保证得到全局最优解；dp[i][k-cost[j]]+val[j]表示选择当前工作，并且不是第一次取。

第二类，最多选一项，即要么不选，一旦选，只能是第一次选。所以状态转移方程为dp[i][k]=max{ dp[i][k],dp[i-1][k-cost[j]]+val[k]}。由于要保证得到全局最优解，所以在该组DP开始以前，应该将上一组的DP结果先复制到这一组的dp[i]数组里，因为这一组的数据是在上一组数据的基础上进行更新的。

第三类，任意选，即不论选不选，选几次都可以，显然状态转移方程为dp[i][k]=max{ dp[i][k],dp[i-1][k-cost[j]]+val[k],dp[i][k-cost[j]]+val[j] }。同样要保证为得到全局最优解，先复制上一组解。

#include <bits/stdc++.h>
#define INF 1000000
#define MAX_LIMT 110
using namespace std;
int n, t;
int dp[MAX_LIMT][MAX_LIMT];
int cost[MAX_LIMT], val[MAX_LIMT];

int main() {
    while(scanf("%d%d", &n, &t) != EOF) {
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++) {
            int m, s;
            scanf("%d%d", &m, &s);
            for(int j = 1; j <= m; j++) {
                scanf("%d%d", &cost[j], &val[j]);
            }
            if(s == 0) {
                for(int j = 0; j <= t; j++) {
                    dp[i][j] = -INF;
                }
                for(int j = 1; j <= m; j++) {
                    for(int k = t; k >= cost[j]; k--) {
                        dp[i][k] = max(dp[i][k], dp[i][k - cost[j]] + val[j]);
                        dp[i][k] = max(dp[i][k], dp[i - 1][k - cost[j]] + val[j]);
                    }
                }
            } else if(s == 1) {
                for(int j = 0; j <= t; j++) {
                    dp[i][j] = dp[i - 1][j];
                }
                for(int j = 1; j <= m; j++) {
                    for(int k = t; k >= cost[j]; k--) {
                        dp[i][k] = max(dp[i][k], dp[i - 1][k - cost[j]] + val[j]);
                    }
                }
            } else {
                for(int j = 0; j <= t; j++) {
                    dp[i][j] = dp[i -1][j];
                }
                for(int j = 1; j <= m; j++) {
                    for(int k = t; k >= cost[j]; k--) {
                        dp[i][k] = max(dp[i][k], dp[i][k - cost[j]] + val[j]);
                        dp[i][k] = max(dp[i][k], dp[i - 1][k - cost[j]] + val[j]);
                    }
                }
            }
        }
        dp[n][t] = max(dp[n][t], -1);
        printf("%d\n", dp[n][t]);
    }
    return 0;
}