7.设有n 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，

1. <?php  
2. /*  
3. *7.设有n 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，  
4. 最大载重量为M，今从n 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，  
5. 而价值的和为最大。  
6. *系统环境:windows/linux  
7. *编译环境:php4/php5  
8. *输入参数:存放在in.txt,多个参数时空格分隔  
9.                     参数1是一组数字,表示一组物品的重量和价值，中间用分号分割,每个物品重量和价值之间用逗号分隔；  
10.                     重量，单位为千克，不能有0,物品的价值，个数必须和重量一样  
11.                     参数3是一个数字，表示最大重量，单位为千克，  
12.                     例如格式：1,1;3,4;2,4;3,7;9,8 10  
13.     输出:out.txt  
14.  
15. */ 
16. $params=getParams(2);  
17. $argv0=trim(trim($params[0]),";");  
18. $argv1=trim($params[1]);  
19. //检查参数1  
20. if(!preg_match_all("/^((\d+,\d+);?)+$/i", $argv0,$matches))  
21. {  
22.     error_msg("params 1 must is group of numbers,break with ; and ,");  
23. }  
24. //检查参数2  
25. if(!is_numeric($argv1))  
26. {  
27.     error_msg("params 3 must be a numbers");  
28. }  
29. $weights=array();  
30. $values=array();  
31. $a=split(";",trim($argv0, ";"));  
32. foreach($a as $s)  
33. {  
34.     $b=split(",",trim($s, ","));  
35.     $weights[]=$b[0];  
36.     $values[]=$b[1];  
37. }  
38.  
39.  
40. if(count($weights)!=count($values))  
41. {  
42.     error_msg("weights count must equal values count");  
43. }  
44. $max_weight=$argv1;  
45. //要在max_weight限制下获取到最大的价值的话，需要计算出每一千克的价值，然后按照从大到小排列  
46. $value_per_weights=array();  
47. foreach($weights as $i => $weight)  
48. {  
49.     if($weight==0)  
50.     {  
51.         error_msg("weight must > 0");     
52.     }  
53.     $value_per_weights[$i]=$values[$i]/$weight;  
54. }  
55. //其中先按照每一千克的价值从大到小排序，重量按照从小到大排序，价值从大到小排序,物品序号不排序  
56. $ar = array ($value_per_weights, $weights,$values,array_keys($values));  
57. array_multisort ($ar[0],SORT_NUMERIC, SORT_DESC,  
58.                  $ar[1], SORT_NUMERIC, SORT_ASC,  
59.                  $ar[2], SORT_NUMERIC, SORT_DESC,$ar[3]);  
60.  
61. $weights_order=$ar[1];  
62. $values_order=$ar[2];  
63. $index_order=$ar[3];  
64. $now_weight=0;  
65. $i=0;  
66. $total=count($weights_order);  
67. $max_value=0;  
68. $find=array();  
69. while(1)  
70. {  
71.     if($now_weight+$weights_order[$i] <= $max_weight)  
72.     {  
73.         $now_weight+=$weights_order[$i];  
74.         $max_value+=$values_order[$i];  
75.           
76.         //统计物品i的个数  
77.         if(isset($find[$index_order[$i]]))  
78.         {  
79.             $find[$index_order[$i]]++;  
80.         }else 
81.         {  
82.             $find[$index_order[$i]]=1;    
83.         }  
84.         if($now_weight==$max_weight)  
85.         {  
86.             break;    
87.         }  
88.     }else{  
89.         $i++;  
90.         if($i >= $total)  
91.         {  
92.             break;    
93.         }  
94.     }  
95. }  
96. //清空out.txt  
97. output("",true);  
98. if(count($find)==0)  
99. {  
100.     output("max weight too small",true);  
101.     error_msg("execute success");  
102. }  
103. //输出结果  
104. output("weight:$now_weight;max value:$max_value");  
105. foreach($find as $index => $num)  
106. {  
107.     output("物品 $index(".$weights[$index].",".$values[$index].") 的个数:$num");  
108. }  
109. error_msg("execute success");  
110.  
111. /*  
112.     从in.txt里读取参数  
113.       
114. */ 
115. function getParams($paramNum)  
116. {  
117.     $in=file_get_contents("in.txt");  
118.     if($in===FALSE){  
119.         error_msg("cannot read in.txt,please check in.txt exists\n");     
120.     }  
121.     $in=preg_replace("/(\s+)/i", " ", $in);  
122.     //多个参数时，按照空格分隔  
123.     $parms=split(" ",trim($in));  
124.     if($parms===FALSE)  
125.     {  
126.         error_msg("cannot get param from in.txt\n");  
127.     }  
128.     if(count($parms) < $paramNum)  
129.     {  
130.         error_msg("it needs $paramNum params\n");  
131.     }  
132.     return $parms;  
133. }  
134.  
135. /*  
136.     把结果输出到输出文件里  
137.     当isClean=true时清空out.txt  
138. */ 
139. function output($msg,$isClean=false)  
140. {  
141.     if($isClean)  
142.     {  
143.     $handle = fopen('out.txt', 'w');  
144.     fclose($handle);      
145.     }  
146.     error_log($msg."\n", 3, "out.txt");  
147. }  
148. /*  
149.     输入错误信息  
150.     如果$is_exit表示输入信息后退出  
151. */ 
152. function error_msg($msg,$is_exit=true)  
153. {  
154.     if($is_exit)  
155.         die($msg."\n");  
156.     else 
157.         echo $msg."\n";  
158. }  
159. ?>