题目一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package class075;

// 多重背包不进行枚举优化
// 宝物筛选
// 一共有n种货物, 背包容量为t
// 每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出
// 请返回选择货物不超过背包容量的情况下，能得到的最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1776
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Code01_BoundedKnapsack {

	public static int MAXN = 101;

	public static int MAXW = 40001;

	public static int[] v = new int[MAXN];

	public static int[] w = new int[MAXN];

	public static int[] c = new int[MAXN];

	public static int[] dp = new int[MAXW];

	public static int n, t;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			in.nextToken();
			t = (int) in.nval;
			for (int i = 1; i <= n; i++) {
				in.nextToken(); v[i] = (int) in.nval;
				in.nextToken(); w[i] = (int) in.nval;
				in.nextToken(); c[i] = (int) in.nval;
			}
			out.println(compute2());
		}
		out.flush();
		out.close();
		br.close();
	}

	// 严格位置依赖的动态规划
	// 时间复杂度O(n * t * 每种商品的平均个数)
	public static int compute1() {
		// dp[0][....] = 0，表示没有货物的情况下，背包容量不管是多少，最大价值都是0
		int[][] dp = new int[n + 1][t + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= t; j++) {
				dp[i][j] = dp[i - 1][j];
				for (int k = 1; k <= c[i] && w[i] * k <= j; k++) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
				}
			}
		}
		return dp[n][t];
	}

题目二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
package class075;

// 多重背包通过二进制分组转化成01背包(模版)
// 宝物筛选
// 一共有n种货物, 背包容量为t
// 每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出
// 请返回选择货物不超过背包容量的情况下，能得到的最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1776
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Code02_BoundedKnapsackWithBinarySplitting {

	public static int MAXN = 1001;

	public static int MAXW = 40001;

	// 把每一种货物根据个数做二进制分组，去生成衍生商品
	// 衍生出来的每一种商品，价值放入v、重量放入w
	public static int[] v = new int[MAXN];

	public static int[] w = new int[MAXN];

	public static int[] dp = new int[MAXW];

	public static int n, t, m;

	// 时间复杂度O(t * (log(第1种商品的个数) + log(第2种商品的个数) + ... + log(第n种商品的个数)))
	// 对每一种商品的个数取log，所以时间复杂度虽然大于O(n * t)，但也不会大多少
	// 多重背包最常用的方式
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			in.nextToken();
			t = (int) in.nval;
			m = 0;
			for (int i = 1, value, weight, cnt; i <= n; i++) {
				in.nextToken(); value = (int) in.nval;
				in.nextToken(); weight = (int) in.nval;
				in.nextToken(); cnt = (int) in.nval;
				// 整个文件最重要的逻辑 : 二进制分组
				// 一般都使用这种技巧，这段代码非常重要
				// 虽然时间复杂度不如单调队列优化的版本
				// 但是好写，而且即便是比赛，时间复杂度也达标
				// 二进制分组的时间复杂度为O(log cnt)
				for (int k = 1; k <= cnt; k <<= 1) {
					v[++m] = k * value;
					w[m] = k * weight;
					cnt -= k;
				}
				if (cnt > 0) {
					v[++m] = cnt * value;
					w[m] = cnt * weight;
				}
			}
			out.println(compute());
		}
		out.flush();
		out.close();
		br.close();
	}

	// 01背包的空间压缩代码(模版)
	public static int compute() {
		Arrays.fill(dp, 0, t + 1, 0);
		for (int i = 1; i <= m; i++) {
			for (int j = t; j >= w[i]; j--) {
				dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
			}
		}
		return dp[t];
	}

}

题目三

1