Knapsack Problem

date: 2021-03-26 excerpt: Knapsack Problem(ナップサック問題)の解き方について

tag: algorithm knapsack problem ナップサック問題 dynamic programming

Knapsack Problem(ナップサック問題)の解き方について

典型的には動的計画法を用いて最適値を計算することができる

ナップサックの世容量をW, アイテムの価値をv, アイテムの大きさをw, アイテムの数をnとすると

大きさm[n+1][W+1]のマトリックスを作る
m[i][j]のマトリックスはm[0][:] = 0かつm[:][0]である
すべてのマトリックスの要素に対してi in 1..W+1, j in 1..n+1まで動的計画法で値を入れていく
- 入れたほうがいい場合, v[i] + m[i-1][j - v[i]]
- 入れないほうがいい場合, m[i-1][j]
- どちらか最大の方を入力する(ただし、wがjより小さい場合)

注意

アイテムの価値が同じものがあっても良い

応用

partitioning souvenirs(パーティションが成立可能か問題)

動作イメージ

pythonによる実装

dp = [[0 for x in range(W+1)] for x in range(H+1)] 
for i in range(1,H+1): 
	for j in range(W+1): 
		if i == 0 or j == 0: 
			dp[i][j] = 0
			continue
        if j >= wt[i]: 
            dp[i+1][j] = max(val[i] + dp[i][j-wt[i]],  dp[i][j]) 
        else: 
            dp[i+1][j] = dp[i][j]
print("result", dp[n][W])

例; 繰り返しのないknapsack問題

問題
0-1 Knapsack Problem
解答

N, W = map(int, input().split())
VW = []
for n in range(N):
    v, w = map(int, input().split())
    VW.append((v, w))

dp = [[0]*(W+10) for _ in range(N+1)]
for i, (v, w) in enumerate(VW):
    for j in range(0, W+10):
        if j >= w:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w] + v)
        else:
            dp[i+1][j] = dp[i][j]
print(dp[-1][W])

例; 繰り返しのあるknapsack問題

問題
Knapsack Problem
解答

N,W=map(int,input().split())

VW=[]
for _ in range(N):
    v,w=map(int,input().split())
    VW.append( (v,w) )
dp = [0]*(W+10)
for v, w in VW:
    for j in range(len(dp)):
        if j >= w:
            dp[j] = max(dp[j-w]+v, dp[j])
print(dp[W])

参考