背包问题

AcWing 2. 01背包问题

二维解法，无优化

package main

import (
	"bufio"
	"fmt"
	"os"
)

func _debug() {
	const eof = 0
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	_i, _n, buf := 0, 0, make([]byte, 1<<12) // 4KB

	// 读一个字符
	rc := func() byte {
		if _i == _n {
			_n, _ = os.Stdin.Read(buf)
			if _n == 0 { // EOF
				return eof
			}
			_i = 0
		}
		b := buf[_i]
		_i++
		return b
	}

	// 读一个整数，支持负数
	ri := func() (x int) {
		neg := false
		b := rc()
		for ; '0' > b || b > '9'; b = rc() {
			// 某些多组数据的题目，不告诉有多少组数据，那么需要额外判断是否读到了 EOF
			if b == eof {
				return
			}
			if b == '-' {
				neg = true
			}
		}
		for ; '0' <= b && b <= '9'; b = rc() {
			x = x*10 + int(b&15)
		}
		if neg {
			return -x
		}
		return
	}
	_ = []interface{}{rc, ri}

	// 01背包
	n, v := ri(), ri()
	weights := make([]int, n)
	value := make([]int, n)

	for i := 0; i < n; i++ {
		weights[i] = ri()
		value[i] = ri()
	}

	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, v+1)
	}

	for i := 1; i <= n; i++ {
		for j := 1; j <= v; j++ {
			if j < weights[i-1] { // 当前背包容量装不下
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = max_i(dp[i-1][j], dp[i-1][j-weights[i-1]]+value[i-1])
			}
		}
	}

	fmt.Fprintln(out, dp[n][v])

}

func max_i(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func main() {
	_debug()
}

一维空间优化解法

package main

import (
	"bufio"
	"fmt"
	"os"
)

func _debug() {
	const eof = 0
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	_i, _n, buf := 0, 0, make([]byte, 1<<12) // 4KB

	// 读一个字符
	rc := func() byte {
		if _i == _n {
			_n, _ = os.Stdin.Read(buf)
			if _n == 0 { // EOF
				return eof
			}
			_i = 0
		}
		b := buf[_i]
		_i++
		return b
	}

	// 读一个整数，支持负数
	ri := func() (x int) {
		neg := false
		b := rc()
		for ; '0' > b || b > '9'; b = rc() {
			// 某些多组数据的题目，不告诉有多少组数据，那么需要额外判断是否读到了 EOF
			if b == eof {
				return
			}
			if b == '-' {
				neg = true
			}
		}
		for ; '0' <= b && b <= '9'; b = rc() {
			x = x*10 + int(b&15)
		}
		if neg {
			return -x
		}
		return
	}
	_ = []interface{}{rc, ri}

	// 01背包
	n, v := ri(), ri()
	weights := make([]int, n)
	values := make([]int, n)

	for i := 0; i < n; i++ {
		weights[i] = ri()
		values[i] = ri()
	}

	dp := make([]int, v+1)

	last := make([]int, v+1)
	for i := 1; i <= n; i++ {
		for j := 1; j <= v; j++ {
			if j < weights[i-1] { // 当前背包容量装不下
				dp[j] = last[j]
			} else {
				dp[j] = max_i(last[j], last[j-weights[i-1]]+values[i-1])
			}
		}
		copy(last, dp)
	}

	fmt.Fprintln(out, dp[v])
}

func max_i(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func main() {
	_debug()
}

最终优化解法

package main

import (
	"bufio"
	"fmt"
	"os"
)

func _debug() {
	// in := bufio.NewReader(os.Stdin)
	const eof = 0
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	_i, _n, buf := 0, 0, make([]byte, 1<<12) // 4KB

	// 读一个字符
	rc := func() byte {
		if _i == _n {
			_n, _ = os.Stdin.Read(buf)
			if _n == 0 { // EOF
				return eof
			}
			_i = 0
		}
		b := buf[_i]
		_i++
		return b
	}

	// 读一个整数，支持负数
	ri := func() (x int) {
		neg := false
		b := rc()
		for ; '0' > b || b > '9'; b = rc() {
			// 某些多组数据的题目，不告诉有多少组数据，那么需要额外判断是否读到了 EOF
			if b == eof {
				return
			}
			if b == '-' {
				neg = true
			}
		}
		for ; '0' <= b && b <= '9'; b = rc() {
			x = x*10 + int(b&15)
		}
		if neg {
			return -x
		}
		return
	}

	// 读一个仅包含小写字母的字符串
	rs := func() (s []byte) {
		b := rc()
		for ; 'a' > b || b > 'z'; b = rc() { // 'A' 'Z'
		}
		for ; 'a' <= b && b <= 'z'; b = rc() { // 'A' 'Z'
			s = append(s, b)
		}
		return
	}
	_ = []interface{}{rc, ri, rs}

	// 01背包问题
	n, v := ri(), ri()

	ws := make([]int, n+1)
	vs := make([]int, n+1)

	for i := 0; i < n; i++ {
		ws[i] = ri()
		vs[i] = ri()
	}
	dp := make([]int, v+1)
	for i := 1; i <= n; i++ {
		for j := v; j >= ws[i-1]; j-- {
			dp[j] = max_i(dp[j], dp[j-ws[i-1]]+vs[i-1])
		}

	}
	fmt.Fprintln(out, dp[v])
}

func max_i(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func min_i(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	_debug()
}

AcWing 3. 完全背包问题

原转移等式,我们将其称其为A

显然，等式A等于（其实就是把一个单独的w拆出来放后面）,我们将其称其为B,红框部分稍后用到

同时我们知道等式C存在

因为max函数的传递性，我们可以使用等式C去替换等式A中红框部分，便可得到：