0-1 ナップザック問題を解決するための PHP 動的プログラミングの分析例_PHP チュートリアル

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

//これは動的計画法の原理に基づいて書いたものです

// max(opt(i-1,w),wi+opt(i-1,w-wi))

//バックパックは最大重量に耐えることができます

$w=15;

//4つのアイテムと各アイテムの重量は次のとおりです

$dx=配列(3,4,5,6);

//各アイテムの価値

$qz=配列(8,7,4,9);

//配列を定義する

$a=配列();

//初期化

for($i=0;$ifor ($j=0;$j//opt(i-1,w),wi+opt(i-1,w-wi)

for ($j=1;$j

for($i=1;$i

$a[$j][$i]=$a[$j-1][$i];

//最大値 w=15 を超えない

if($dx[$j-1]<=$w){

if(!isset($a[$j-1][$i-$dx[$j-1]])) 続行;

//wi+opt(i-1,wi)

$tmp = $a[$j-1][$i-$dx[$j-1]]+$qz[$j-1];

//opt(i-1,w),wi+opt(i-1,w-wi) => 比較

if($tmp>$a[$j][$i]){

$a[$j][$i]=$tmp;

}

}

}

}

//この配列を出力し、最も高い値を持つ右端の値を出力します

for ($j=0;$j

for ($i=0;$i

echo $a[$j][$i]."/t";

} echo "/n";

}

?>