企业官网建设流程全解析

写在前面

背包DP是普及组比较重要的算法之一，用于解决贪心解决不了的问题

先看题

描述

一个旅行者有一个最多能装 M 公斤的背包，现在有 n 件物品，它们的重量分别是 W1​,W2​,...,Wn​,它们的价值分别为 C1​,C2​,...,Cn​，求旅行者能获得最大总价值。

输入描述

第 1 行：两个整数，M （背包容量，M≤200 ）和 N ( 物品数量，N≤30 )。
第 2…N+1 行：每行二个整数 Wi​,Ci​，表示每个物品的重量和价值。

输出描述

仅一行，一个数，表示最大总价值。

样例输入 1

10 4 2 1 3 3 4 5 7 9

样例输出 1

12

提示

M≤200，N≤30

分析

先尝试暴力：枚举每一个物品要或不要需要θ（2^30），显然会出现 time limit exceed 的问题。怎么办？

众所周知，一般地，背包容量越大，在物体价值、重量一定的情况下，背包容量越大，理论上总价值越大。那么我们可不可以声明一个数组dp[2009]，使dp[i]表示容积为i时的最大价值？试试就逝世试试

for (int i = 1; i <= n; i++) { for (int j = m; j >= w[i]; j--) {//01背包因为物品只有一件，不能重复选择，每个数据在上一轮的基础上产生 dp[j] = max(dp[j], c[i] + dp[j - w[i]]); } }

恭喜你，发明了01背包算法，该算法的状态转移方程一般为

dp[j] = max(dp[j], c[i] + dp[j - w[i]]);

再看第二道题

描述

设有 n 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为 M，今从 n 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于 M，而价值的和为最大。

输入描述

第一行：两个整数，M ( 背包载重，M≤200 )和 N ( 物品数量，N≤30 )。
第 2…N+1 行：每行二个整数 Wi​,Ci​，表示每个物品的重量和价值。

输出描述

仅一行，一个数，表示最大总价值。

样例输入 1

10 4 2 1 7 9 1 1 4 5

样例输出 1

12

提示

M≤200，N≤30

分析

两道题唯一的区别在于是否可以“重复选取”。

如果我们还用01背包问题的状态转移方程，再这样的样例中就会错得非常离谱

样例输入 样例输出 10 4 10000000 54188 1 114514 1 396396 1 1 1000000

我们的答案将会为1000000，与标准答案差得很远。

有同学说：这好办啊，把01背包加一层while不就行了吗？

确实，针对本题可行，但是如果数据量变成类似1≤m,n≤5*10^7且m*n≤5*10^7就不可行了。

那么，又有同学说，把上一题中内层循环从倒序改为顺序不就行了吗？

于是

for (int i = 1; i <= n; i++) { for (int j = w[i]; j <= m; j++) { dp[j] = max(dp[j], c[i] + dp[j - w[i]]); } }

恭喜你，发明了完全背包算法，该算法的状态转移方程依旧为

dp[j] = max(dp[j], c[i] + dp[j - w[i]]);

但是变成顺序循环

最后看一道题

描述

有 N 种物品和一个容量是 M 的背包。
第 i 种物品最多有 si 件，每件体积是 wi，价值是 ci。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入描述

第一行两个整数，N，M，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 wi,ci,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出描述

输出一个整数，表示最大价值。

样例输入 1

4 5 1 2 3 2 4 1 3 4 3 4 5 2

样例输出 1

10

提示

0<N≤5000
0<M≤5000
0<ci,wi,si≤5000

分析

有同学说：这好办啊，把01背包加一层for不就行了吗？

但是，本题数据显然不允许这样的操作

学过《人教版物理（八年级上册）》中用托盘天平测量质量这一课的同学或许会想到老师上课问的一个问题：为什么砝码质量分别为500g,200g,200g,100g,50g,20g,20g,10g，游码质量为0~5.0g？

原因很简单：用这些可以组成0~1105.0g中间的任何一种情况（保留一位小数）。

那么，如果将这类背包算法进行如下改动是不是就可以了呢？

int a[n * 30], b[n * 30], q = 0; // 注意，大数组建议开在全局中 for (int i = 1; i <= n; i++) { for (int j = 1; ((j << 1) - 1) * w[i] <= m && ((j << 1) - 1) <= s[i]; j << 1) { a[++q] = j * c[i]; b[q] = j * w[i]; if ((j << 1) - 1 > s[i]) { a[++q] = (s[i] + 1 - (j << 1)) * c[i]; b[q] = (s[i] + 1 - (j << 1)) * w[i]; } } }

然后再进行

for (int i = 1; i <= q; i++) { for (int j = m; j >= b[i]; j--) { dp[j] = max(dp[j], dp[j - b[i]] + a[i]); } }

恭喜你，又发明了多重背包算法，其状态转移方程为

dp[j] = max(dp[j], dp[j - b[i]] + a[i]);

写在最后/声明

文章为本蒟蒻原创，欢迎各位dalao点赞收藏，并提出您宝贵的建议