ダイナミックプランニング0-1リュック問題

1919 ワード
問題の説明:
Nの中の品物とリュックサックを1つ与えます.アイテムiの重量はWiで、その価値ビットVi、リュックサックの容量はCです.リュックサックに入るものをどのように選んで、リュックサックに入るものの総価値を最大にするべきですか?
物品を選択する際、各物品iには、リュックサックに入れるか、リュックサックに入れないかの2つの選択しかない.物iを複数回入れたり、物の一部だけ入れたりすることはできません.そのため、この問題は0-1リュックサック問題と呼ばれている. 
 
問題解析:V(i,j)を前i(1<=i<=n)個の物品にj(1<=j<=C)のリュックサックに入れることができる物品の最大価値を示すと,次のような動的計画関数が得られる.
(1)   V(i,0)=V(0,j)=0 
(2)   V(i,j)=V(i-1,j)  j       V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) } j>wi
(1)式は、i番目の物品の重量がリュックサックの容量より大きい場合、人を入れる前のi個の物品が得た最大価値と、前のi−1個の物品が得た最大価格は同じであり、すなわち、物品iがリュックサックに入れられないことを示す.第(2)の式は、第iの物品の重量がリュックサックの容量より小さい場合、(a)第iの物品をリュックサックに入れると、リュックサックの物品の価値は、第i-1の物品が容量位j-wiのリュックサックに入れる価値に第iの物品の価値viを加えることに等しい.(b)i番目の物品がリュックサックに入れられていない場合、リュックサックにおける物品価値は、前のi−1個の物品を容量jのリュックサックに入れて得られた価値に等しい.明らかに,両者の中で最も価値のあるのは,前のi個の物品を容量jのリュックサックに入れる最適解である.
package main

import (
	"fmt"
)

const (
	N = 4
	W = 5
)

var weight []int = []int{3, 2, 1, 2}
var value []int = []int{4, 3, 2, 2}
var record [N][W + 1]int //         

func init() {
	for i := 0; i < N; i++ {
		for j := 0; j <= W; j++ {
			record[i][j] = -1
		}
	}
}

func show() {
	for i := 0; i < N; i++ {
		for j := 0; j <= W; j++ {
			fmt.Printf("%v ", record[i][j])
		}
		fmt.Printf("
")
	}
}

func solve(i int, total int) int {

	result := 0
	if i >= N {
		return result
	}

	if -1 != record[i][total] {
		return record[i][total]
	}

	if weight[i] > total {
		record[i][total] = solve(i+1, total)
	} else {
	        //      
		result = max(solve(i+1, total), solve(i+1, total-weight[i])+value[i])
	}

	record[i][total] = result

	return record[i][total]
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	result := solve(0, W)
	fmt.Printf("best value:%v 
", result)

}

まとめ:動的計画は第N+1回の最優解と第N回の最優解の間に関連があることを求めて、裁断した探索と遡及アルゴリズムと理解することができる
動的計画の正体を暴露する--アルゴリズム第3章のオンライン実践報告
ツリーの一般的なアルゴリズム操作