java---dp动态规划---多重背包（每日一道算法2022.10.9）

110 阅读 0 评论 73 点赞

我是靠谱客的博主单纯豆芽，最近开发中收集的这篇文章主要介绍java---dp动态规划---多重背包（每日一道算法2022.10.9），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

注意事项：
最好先理解01背包和完全背包：
java—dp动态规划—完全背包
java—dp动态规划—01背包

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

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

0 < N ≤ 1000
0 < V ≤ 2000
0 < vi,wi,si ≤ 2000

输出：
10

public class 动态规划_多重背包 {
//这里开25000是因为2000 * log(1000)也就是24000，以防万一再开大一点
//v是体积，w是价值
public static int N = 25000, n, m;
public static int[] v = new int[N], w = new int[N];
public static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
n = in.nextInt(); m = in.nextInt();
op_multi();
}
//基础版，时间复杂度为O(n^3)
public static void base_multi() {
int[][] f = new int[N][N];
int[] s = new int[N]; //s存储个数
//读入数据
for (int i = 1; i<=n; i++) {
v[i] = in.nextInt(); w[i] = in.nextInt(); s[i] = in.nextInt();
}
//状态计算
for (int i = 1; i<=n; i++) {
for (int j = 0; j<=m; j++) {
//这里的判断条件是和完全背包唯一的区别，完全背包可以选无数个，但多重背包最多只能选s[i]个
for (int k = 0; k*v[i] <= j && k <= s[i]; k++) {
f[i][j] = Math.max(f[i][j], f[i-1][j - k*v[i]] + k*w[i]);
}
}
}
System.out.println(f[n][m]);
}
//优化版，使用到了优化01背包，同时进行二进制优化，时间复杂度为O(n^2乘logS)
public static void op_multi() {
int[] f = new int[N];
int count = 0;
//count表示当前是第几堆
for (int i = 1; i<=n; i++) {
int a = in.nextInt(), b = in.nextInt(), s = in.nextInt(); //当前物品的体积，价值，个数
//通过二进制进行优化，每次从s中拿取k，k为2^0,2^1,2^2...直到无法拿出，每次都分为一堆
int k = 1;
while (k <= s) {
count++;
v[count] = a * k;
w[count] = b * k;
s -= k;
k <<= 1;
}
//如果s还有剩下，那么就将其分为新的一堆
if (s > 0) {
count++;
v[count] = a * s;
w[count] = b * s;
}
}
//一维01背包，这里注意是用count作为界限，现在是要对所有堆进行处理
for (int i = 1; i<=count; i++) {
for (int j = m; j>=v[i]; j--) {
f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
}
}
System.out.println(f[m]);
}
}