背包问题（三）--多重背包
多重背包模型
背包容量为V，有N件物品，每件物品的体积是vi，价值是wi，第i件物品最多有mi件可用。求将物品装入背包获得的最大价值
思路
f(i,v)表示前i件商品，背包容量不大于v时的最大价值
f(i,v) = max(f(i-1,v-kc[i])+kwi) 0<=k<=mi
代码实现
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N + 1];
int[] w = new int[N + 1];
int[] s = new int[N + 1];
for (int i = 1; i <= N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
int[][] dp = new int[N + 1][V + 1];
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
for (int k = 0; k <= s[i] && j >= k * v[i]; k++) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * v[i]] + k*w[i]);
}
}
}
System.out.println(dp[N][V]);
}
}
复杂度优化
二进制优化：
通过数字1，2可以拼出1~3的任意数字
通过1，2，4可以拼出1~7的任意数字
通过1，2，4，8可以拼出1~15的任意数字
...
由此，对于第i件物品，如果有1023件，那我们可以用1，2，4，8，16，32，64，...，512拼出1023件物品
1，2，4，8，16，32...可以看成是01背包，要么选择1件商品，要么不选，...，要么选择32件商品，要么不选
本来想要凑出1~n个数需要O(n)的复杂度，现在只需要O(logn)的复杂度
总得来说，就是将每个物品分为logm份，然后做01背包。总得复杂度O(NVlogm)
import java.util.Scanner;
public class Main2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[12010]; // N * log(每种物品最多的数量)
int[] w = new int[12010];
int cnt = 0;
for (int i = 1; i <= N; i++) {
int a = sc.nextInt(); // 第i种物品的体积
int b = sc.nextInt(); // 第i种物品的价值
int c = sc.nextInt(); // 第i种物品的数量
int k = 1;
while (k <= c) {
cnt++;
v[cnt] = a * k;
w[cnt] = b * k;
c -= k;
k *= 2;
}
if (c > 0) {
cnt++;
v[cnt] = a * c;
w[cnt] = b * c;
}
}
// 01背包
N = cnt;
int[][] dp = new int[N + 1][V + 1];
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
dp[i][j] = dp[i - 1][j];
if(j>=v[i]){
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
}
System.out.println(dp[N][V]);
}
}
对上面的01背包优化
// 01背包
N = cnt;
int[] dp = new int[V + 1];
for (int i = 1; i <= N; i++) {
for (int j = V; j >= v[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
System.out.println(dp[V]);
记录路径
leetcode798 得分最高的最小轮调
给定一个数组 A，我们可以将它按一个非负整数 K 进行轮调，这样可以使数组变为 A[K],
A[K+1], A{K+2], ... A[A.length - 1], A[0], A[1], ..., A[K-1] 的形式。此后，任何值小于或等于其
索引的项都可以记作一分。
例如，如果数组为 [2, 4, 1, 3, 0]，我们按 K = 2 进行轮调后，它将变成 [1, 3, 0, 2, 4]。这将记
作 3 分，因为 1 > 0 [no points], 3 > 1 [no points], 0 <= 2 [one point], 2 <= 3 [one point], 4 <= 4
[one point]。
在所有可能的轮调中，返回我们所能得到的最高分数对应的轮调索引 K。如果有多个答案，返
回满足条件的最小的索引 K。
示例 1：
输入：[2, 3, 1, 4, 0]
输出：3
解释：
下面列出了每个 K 的得分：
K = 0, A = [2,3,1,4,0], score 2
K = 1, A = [3,1,4,0,2], score 3
K = 2, A = [1,4,0,2,3], score 3
K = 3, A = [4,0,2,3,1], score 4
K = 4, A = [0,2,3,1,4], score 3
所以我们应当选择 K = 3，得分最高。
示例 2：
输入：[1, 3, 0, 2, 4]
输出：0
解释：
A 无论怎么变化总是有 3 分。
所以我们将选择最小的 K，即 0。
提示：
A 的长度最大为 20000。
A[i] 的取值范围是 [0, A.length]。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-rotation-with-highest-score
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
leetcode799 香槟塔
我们把玻璃杯摆成金字塔的形状，其中第一层有1个玻璃杯，第二层有2个，依次类推到第100
层，每个玻璃杯(250ml)将盛有香槟。
从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流
量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯
子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上）
例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各
自盛放一半的香槟。在倒三杯香槟后，第二层的香槟满了 - 此时总共有三个满的玻璃杯。在倒
第四杯后，第三层中间的玻璃杯盛放了一半的香槟，他两边的玻璃杯各自盛放了四分之一的香
槟，如下图所示。
现在当倾倒了非负整数杯香槟后，返回第 i 行 j 个玻璃杯所盛放的香槟占玻璃杯容积的比例（i
和 j都从0开始）。
示例 1:
输入: poured(倾倒香槟总杯数) = 1, query_glass(杯子的位置数) = 1, query_row(行数) = 1
输出: 0.0
解释: 我们在顶层（下标是（0，0））倒了一杯香槟后，没有溢出，因此所有在顶层以下的玻
璃杯都是空的。
示例 2:
输入: poured(倾倒香槟总杯数) = 2, query_glass(杯子的位置数) = 1, query_row(行数) = 1
输出: 0.5
解释: 我们在顶层（下标是（0，0）倒了两杯香槟后，有一杯量的香槟将从顶层溢出，位于
（1，0）的玻璃杯和（1，1）的玻璃杯平分了这一杯香槟，所以每个玻璃杯有一半的香槟。
注意:
poured 的范围[0, 10 ^ 9]。
query_glass 和query_row 的范围 [0, 99]。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/champagne-tower
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
image.png
美团工作强度 2455人发布