[学習記録]AtCoder EDP E-Knapsack 2[Go]

問題

問題文

N 個の品物があります。 品物には 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、品物 i の重さは wi​ で、価値は vi​ です。

太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量はW であり、持ち帰る品物の重さの総和は W 以下でなければなりません。

太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

制約

• 入力はすべて整数である。

• 1≤N≤100

• 1≤W≤10^9

• 1≤wi​≤W

• 1≤vi​≤10^3

解法

問題文はD - Knapsack1と同じだが、制約が異なる。そのため、Dと同じ解法で行うとTLEとなる。
価値の総和の最大は、10^ 3 × 100 = 10 ^5と、使えそうなので、こちらを用いて問題を解く。

i 番目までの品物を使って、ちょうど価値 j にしたときの最小重さを記録しておくと、価値が高いほうから最小重さを見ていき、初めてW以下となったときの価値が回答になる。

dp := make([][]int, n+1)
max_value := 1_000 * 100

ans := 0
for i := max_value; i >= 0; i-- {
	if dp[n][i] <= w {
		ans = i
		break
	}
}

dpの計算はDと同じように、i -1番目を入れた場合、入れない場合での最小重さを計算する。ただし、dpの初期化は重さの最大を超える値でしておく。
そもそも選択できないときのガードも同様に追加する。

dp := make([][]int, n+1
over_weight := 1_000_000_000*100 + 1

dp[0] = initSliceAs(max_value+1, over_weight)

for i := 1; i <= n; i++ {
    dp[i] = initSliceAs(max_value+1, over_weight)
	weight := sli[i-1][0]
	value := sli[i-1][1]
	for j := 1; j <= max_value; j++ {
		if j-value < 0 {
            dp[i][j] = dp[i-1][j]
			continue
		}

		// 入れる
        in := dp[i-1][j-value] + weight
		// 入れない
		not_in := dp[i-1][j]

		dp[i][j] = Min(in, not_in)
	}
}

品物を入れないときは 価値 = 0とするため、dpの初期値を 0 で更新する。

dp[0] = initSliceAs(max_value+1, over_weight)
dp[0][0] = 0

// i loop
for {}

// 入力例３の時のdp（抜粋）
[0 100000000001 100000000001 100000000001 100000000001 100000000001 100000000001 100000000001 100000000001 100000000001]
[0 100000000001 100000000001 100000000001 100000000001 6 100000000001 100000000001 100000000001 100000000001]
[0 100000000001 100000000001 100000000001 100000000001 6 5 100000000001 100000000001 100000000001]
[0 100000000001 100000000001 100000000001 6 6 5 100000000001 100000000001 12]
[0 100000000001 100000000001 100000000001 6 6 5 100000000001 100000000001 12]
[0 100000000001 100000000001 100000000001 6 3 5 100000000001 100000000001 9]
[0 100000000001 7 100000000001 6 3 5 10 12 9]

解法のポイント

「～となる〇〇の最大値」を値に持つDPは、適当な添字と入れ替えて「～となる××の最小値」というDPにできることが多い

https://kyopro-friends.hatenablog.com/entry/2019/01/12/230931

制約から ｖを添え字として、そして入れ替えできる可能性から最小値をdpとして持つことから、解法を考える。

コード（AC)

func run() interface{} {
	n, w := readInt(), readInt()

	sli := make([][]int, n)
	for i := 0; i < n; i++ {
		sli[i] = readSli(2)
	}

	dp := make([][]int, n+1)
	max_value := 1_000 * 100
	over_weight := 1_000_000_000*100 + 1

	dp[0] = initSliceAs(max_value+1, over_weight)
	dp[0][0] = 0

	for i := 1; i <= n; i++ {
		dp[i] = initSliceAs(max_value+1, over_weight)
		weight := sli[i-1][0]
		value := sli[i-1][1]
		for j := 0; j <= max_value; j++ {
			if j-value < 0 {
				dp[i][j] = dp[i-1][j]
				continue
			}

			in := dp[i-1][j-value] + weight
			not_in := dp[i-1][j]

			dp[i][j] = Min(in, not_in)
		}
	}

	ans := 0
	for i := max_value; i >= 0; i-- {
		if dp[n][i] <= w {
			ans = i
			break
		}
	}

	return ans
}

反省点等

dpの初期化を 0 で行ったり、dp[ i ][ j ] = (価値がjを超えるように選んだ時の最小重さ）としたときでも解くことはできたが、余計な処理を多分に入れる必要があった。