完全背包问题(go实现)

1.题目

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式：

​ 第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

​ 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式：

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

数据范围：

​ 0<N,V≤1000

​ 0<vi,wi≤1000

2.解题思路及代码实现

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
package main

import "fmt"

func main() {
	/*
	   题目：
	   有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

	   第 i 种物品的体积是 vi，价值是 wi。

	   求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
	   输出最大价值。

	   输入格式
	   第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

	   接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

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

	   数据范围
	   0<N,V≤1000
	   0<vi,wi≤1000
	*/
	simplicity()
	// optimize()
}

func max(x, y int) int {
	if x < y {
		return y
	}
	return x
}

func simplicity() {

	/*
		1.朴素解法
		状态表示：f[i][j] 表示考虑前i个物品的情况下，总体积为j时的最大价值。

		转移方程：
		1.不考虑i个物品的情况
		f[i][j] = f[i-1][j]

		2.考虑第i个物品的情况
		f[i][j] = f[i-1][j-k*v[i]]+k*w[i]  k在体积足够的情况下穷举

		汇总：
		f[i][j] = max{f[i-1][j],f[i-1][j-k*v[i]]+k*w[i]} k在体积足够的情况下穷举


		复杂度：
		时间复杂度O(N*V*K)
		空间复杂度O(N*V)

	*/

	const N = 1010
	var n, m int
	var v, w [N]int
	var f [N][N]int

	fmt.Scanf("%d %d\n", &n, &m)
	for i := 1; i <= n; i++ {
		fmt.Scanf("%d %d\n", &v[i], &w[i])
	}

	for i := 1; i <= n; i++ {
		for j := m; j >= v[i]; j-- {
			for k := 0; k*v[i] <= j; k++ {
				f[i][j] = max(f[i-1][j], f[i-1][j-k*v[i]]+k*w[i])
			}
		}
	}
	fmt.Println(f[n][m])
}

func optimize() {
	/*
		2.优化实现
		状态表示：f[i]表示总体积为i时的最大价值。

		转移方程：
		for i=1...n
		for j=0...m
		f[j]= max{f[j], f[j - v[i]] + w[i]}

		复杂度：
		时间复杂度O(VN)
		空间复杂度O(V)


		证明一下转移方程的正确性（数学归纳法）：
		初始条件：f[0] = 0
		1、假设考虑前i-1个物品之后，所有的f[j]是正确的。
		2、证明： 考虑完i个物品之后，所有的f[j]是正确的。

		对某个j而言，如果最优解中包含k个v[i]，
		则有：
		f[j - k*v[i]] 不包含第i个物品的情况；此时所有的f[j]是正确的。 ------ （假设条件）

		递推：
		转移方程：	f[j] = max{ f[j], f[j - v[i]] + w[i] }
		则
		f[j] = max{f[j],f[j - (k-1)*v[i] -v[i]] + w[i]}  包含1个v[i]的情况
		...
		f[j] = max{f[j], f[j - v[i]] + w[i]} 包含k-1个v[i]的情况
		f[j] = max{f[j], f[j]} 包含k个v[i]的情况
		表明，在考虑完第i个物品之后，所有的f[j]也是正确的。
		证毕。
	*/
	const N = 1010
	var n, m int
	var v, w [N]int
	var f [N]int

	fmt.Scanf("%d %d\n", &n, &m)
	for i := 1; i <= n; i++ {
		fmt.Scanf("%d %d\n", &v[i], &w[i])
	}

	for i := 1; i <= n; i++ {
		for j := 0; j <= m; j++ {
			if j >= v[i] {
				f[j] = max(f[j], f[j-v[i]]+w[i])
			}
		}
	}
	fmt.Println(f[m])
}