PHP贪婪算法解决0-1背包问题实例分析

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

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

//0-1背包贪心算法问题

class tanxin{

public $weight;

public $price;

public function __construct($weight=0,$price=0)

{

$this->weight=$weight;

$this->price=$price;

}

}

//生成数据

$n=10;

for($i=1;$i<=$n;$i++){

$weight=rand(1,20);

$price=rand(1,10);

$x[$i]=new tanxin($weight,$price);

}

//输出结果

function display($x)

{

$len=count($x);

foreach($x as $val){

echo $val->weight,' ',$val->price;

echo '<br>';

}

}

//按照价格和重量比排序

function tsort(&$x)

{

$len=count($x);

for($i=1;$i<=$len;$i++)

{

for($j=1;$j<=$len-$i;$j++)

{

$temp=$x[$j];

$res=$x[$j+1]->price/$x[$j+1]->weight;

$temres=$temp->price/$temp->weight;

if($res>$temres){

$x[$j]=$x[$j+1];

$x[$j+1]=$temp;

}

}

}

}

//贪心算法

function tanxin($x,$totalweight=50)

{

$len=count($x);

$allprice=0;

for($i=1;$i<=$len;$i++){

if($x[$i]->weight>$totalweight) break;

else{

$allprice+=$x[$i]->price;

$totalweight=$totalweight-$x[$i]->weight;

}

}

if($i<$len) $allprice+=$x[$i]->price*($totalweight/$x[$i]->weight);

return $allprice;

}

tsort($x);//按非递增次序排序

display($x);//显示

echo '0-1背包最优解为:';

echo tanxin($x);