[学習記録]AtCoder EDP D-Knapsack 1[Go]

問題

問題文

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

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

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

制約

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

• 1≤N≤100

• 1≤W≤10^5

• 1≤wi​≤W

• 1≤vi​≤10^9

解法

i 番目までの品物を使って、重さ j になったときの、価値の最大値を記録する

	for i := 1; i <= n; i++ {
		for j := 1; j <= w; j++ {
            // dpに記録
		}
	}

i 番目の品物を使うとき、使わないときそれぞれの値を計算し、それをdp に記録する。

• 使うときは、 i -1番目品物まで使い j - (i 番目の品物の重さ) の時の価値　に i番目の品物の価値を加えたものになる。

• 使わないときは、i -1番目まで使った時と同じ価値になる。

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

dp[i][j] = Max(in, not_in)

j より品物の重さが大きいとき、その品物は使えない。そのため、ガードを追加する。

// そもそも入れられない
if weight > j {
    // not_inと同じパターン
	dp[i][j] = dp[i-1][j]
	continue
}

i =1の時、i -1(=0)番目まで使った時の価値が必要になるため、
dpをn +1, w +1で初期化する

dp := make([][]int, n+1)
	
　　　// ...
　　　dp[i] = make([]int, w+1)

全て計算した後、dp[n]][w]が回答になる。
（ n番目の品物まで使い、重さwとなったときの価値の最大値）

コード（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)
	dp[0] = make([]int, w+1)
	for i := 1; i <= n; i++ {
		dp[i] = make([]int, w+1)
		weight := sli[i-1][0]
		value := sli[i-1][1]
		for j := 1; j <= w; j++ {
			// そもそも入れられない
			if weight > j {
				dp[i][j] = dp[i-1][j]
				continue
			}

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

			dp[i][j] = Max(in, not_in)
		}
	}
	ans := dp[n][w]
	return ans
}