给定物品n件，他们的重量分别是w[0]，w[1]，……w[n-1]，物品的价值分别为v[0]，v[1]，……v[n-1]，另有一个背包，它可以容纳的总重量为w。设计一种物品挑选方案，要求从这n件物品中所选取的物品的总重量不超过背包的容量w，使选中物品的价值之和最大。
这个题至少要一个小时， 我说思路， 让别人做吧。
1. 对w的数组排序, 选出小于w重量的项(赋值数组p),
2. 对p数组计算笛卡尔积乘积阵列，选出所有子集里的项的和小于w重量的子集(赋值数组r)，
3. 对r数组里的每个子集里的项转换成相对应的v值， 并分别求和（赋值数组wv),
4. 对wv数组排序， 得出对大的值的键就是结果。
2 ...... 选出所有子集里的项的和小于w重量的子集
-----------------------------
就是对子集项求和， 如
{1,3,5} --> (1+3+5) {2,6} --> (2+6)
另外， 这个和回溯算法有点不同， 回溯算法计算出来的子集是有顺序的，
这里的需求计算出来的子集是没顺序的 ， 更像是计算笛卡尔乘积多点。
coolesting思路不错
其实这道题的思路网络上早就有了，
有用C写的，也有用C++写的,甚至C#都有，就是没有用PHP写的
所以想看看我们csdn的PHP版块是否有热心人愿意用PHP写一个
别到时候百度时候找不到PHP写的回溯案例
coolesting思路不错
其实这道题的思路网络上早就有了，
有用C写的，也有用C++写的,甚至C#都有，就是没有用PHP写的
所以想看看我们csdn的PHP版块是否有热心人愿意用PHP写一个
别到时候百度时候找不到PHP写的回溯案例
好,这个伟大的任务就交给你了......
为验证算法的正确性，建议给出原始数据和答案
算法不难，从其他语言移植过来就可以。当然有创新就更好了
1. 对w的数组排序, 选出小于w重量的项(赋值数组p),
2. 对p数组计算笛卡尔积乘积阵列，选出所有子集里的项的和小于w重量的子集(赋值数组r)，
第一步只产生了一维数组，那么第二步的笛卡尔积如何计算呢？
如果是求组合，那倒还简单
唠叨老大没看出来吗，一楼用的是穷举法，所有的组合先统计出来，然后一项项去比对
引用 1 楼 coolesting 的回复:
1. 对w的数组排序, 选出小于w重量的项(赋值数组p),
2. 对p数组计算笛卡尔积乘积阵列，选出所有子集里的项的和小于w重量的子集(赋值数组r)，
第一步只产生了一维数组，那么第二步的笛卡尔积如何计算呢？
如果是求组合，那倒还简单 他说错了吧，应该是求第一步产生的一维数组的闭包吧
可不可以这样考虑，在所有小于所需物品重量的组合中，用物品的价值除以物品的重量，得到一个比值，对此比值进行由大至小排序，从前面找出小于等于所需重量中最大比值的组合。
$ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2'=>'9','12'=>'8','9'=>'12','10'=>'15','15'=>'6');
$a=array();
$w=10;//所需重量
foreach($ar as $key=>$value){
if($key }
//print_r($a);
foreach($a as $key=>$value){
$a[$key]=$value/$key;
}
arsort($a);
//print_r($a);
$sum=0;
$b=array();
foreach($a as $key=>$value){
$sum=$sum+$key;
if($sum>$w){break;};
$b[$key]=$ar[$key];
}
print_r($b);
可不可以这样考虑，在所有小于所需物品重量的组合中，用物品的价值除以物品的重量，得到一个比值，对此比值进行由大至小排序，从前面找出小于等于所需重量中最大比值的组合。
$ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2'=>'9','12'=>'8','9'=>'12','10'=>'15','15'=>'6');
$a=array();
$…… 不行的，举一个例子，我有9=>8，4=>3，10=>10，三个物品，背包为11，你的算法出来是10=>10，而显然应该是9=>8,4=>3是对的
可不可以这样考虑，在所有小于所需物品重量的组合中，用物品的价值除以物品的重量，得到一个比值，对此比值进行由大至小排序，从前面找出小于等于所需重量中最大比值的组合。
$ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2'=>'9','12'=>'8','9'=>'12','10'=>'15','15'=>'6');
$a=array();
$……
像这样 就不能出现 两个价格相同的物品啦；所以说不去全面
可不可以这样考虑，在所有小于所需物品重量的组合中，用物品的价值除以物品的重量，得到一个比值，对此比值进行由大至小排序，从前面找出小于等于所需重量中最大比值的组合。
$ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2'=>'9','12'=>'8','9'=>'12','10'=>'15','15'=>'6');
$a=array();
$w……
我是用键表示重量，值表示价格。
<?php$m = 15;$arr = array(array(2,1),array(4,2),array(3,6),array(5,9),array(9,8));//第一个值为价格 ；第二个值为 重量function Combination($arr, $size = 1) { $len = count ( $arr ); $max = pow ( 2, $len ) - pow ( 2, $len - $size ); $min = pow ( 2, $size ) - 1; $r_arr = array (); for($i = $min; $i <= $max; $i ++) { $t_arr = array (); for($j = 0,$k = 0; $j < $len; $j ++) { $a = pow ( 2, $j ); $t = $i & $a; if ($t == $a) { $t_arr [] = $arr [$j]; } } if (count($t_arr) == $size) { $r_arr [] = $t_arr; } } return $r_arr;}$num = count($arr);for($i = 1;$i<=$num;$i++){ $_tt = Combination($arr,$i); $num_tt = count($_tt); for($j = 0;$j<$num_tt;$j++){ $_t[] = $_tt[$j]; }}//找出所以的可能情况function check_m($arr,$m,$jk=1) {//$arr 为要判断的数组 $m为重量 $jk为判断的是重量还是价格 $num_t = count($arr); for($i = 0;$i <$num_t ;$i++){ $num_ti = count($arr[$i]); $as = 0; for($j=0;$j<$num_ti;$j++){ $as += $arr[$i][$j][$jk]; } if($as<=$m){ $_r[] =$arr[$i]; } } Return $_r;}function check_max($arr) { $ms = 0; $num_t = count($arr); for($i = 0;$i <$num_t ;$i++){ $num_ti = count($arr[$i]); $as = 0; for($j=0;$j<$num_ti;$j++){ $as += $arr[$i][$j][0]; } if($as>=$ms){ $_r = $arr[$i]; } $ms = $as; } Return $_r;}$_rr = check_m($_t,$m,1);$_r=check_max($_rr);echo "<pre class="brush:php;toolbar:false">";print_r($_r);echo " 引用 10 楼 blizzf99 的回复:
可不可以这样考虑，在所有小于所需物品重量的组合中，用物品的价值除以物品的重量，得到一个比值，对此比值进行由大至小排序，从前面找出小于等于所需重量中最大比值的组合。
$ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2'=>'9','12'=>'8','9'=>'12','10'=>'15','15……
确实是没考虑到重量相同的情况，如果重量相同，应该取价格高的那个。
class Backtracking { private $c = 0; //背包容量 private $n = 0; //物品数 private $w = array(); //物品重量数组 private $p = array(); //物品价值数组 private $cw = 0; //当前重量 private $cp = 0; //当前价值 private $bestp = 0; //当前最优价值 private $d; //单位重量价值 private $st = array(); function __construct($w, $p, $c) { $this->w = $w; $this->p = $p; $this->c = $c; $this->n = count($w); $this->d = array_map(array($this, 'Calculation'), $this->p, $this->w); array_multisort($this->d, SORT_DESC, $this->w, $this->p); } private function Calculation($p, $w) { if($w == 0) return $p; return $p / $w; } function BestValue() { return $this->bestp; } function parse($i=0) { if($this->debug) echo "-> $i ($this->cw, $this->cp) [".join(',', $this->st)."]<br />\n"; if($i > $this->n - 1) { //到达叶子节点 $this->bestp = $this->cp; if($this->debug) echo "<= $i ($this->cw, $this->cp) [".join(',', $this->st)."]<br />\n"; return; } $this->st[] = $i; if($this->cw + $this->w[$i] <= $this->c) { $this->cw += $this->w[$i]; $this->cp += $this->p[$i]; $this->parse($i + 1); //深度优先 $this->cw -= $this->w[$i]; $this->cp -= $this->p[$i]; } if($this->Bound($i + 1) > $this->bestp) { //向前探测 if($this->debug) echo "== $i ($this->cw, $this->cp) [".join(',', $this->st)."]<br />\n"; array_pop($this->st); $this->parse($i + 1); } if($this->debug) echo "<- $i ($this->cw, $this->cp) [".join(',', $this->st)."]<br />\n"; } private function Bound($i) { //计算节点所相应价值的上界 $cleft = $this->c - $this->cw; //剩余容量 $b = $this->cp; //以物品单位重量价值递减顺序装入物品 while($i < $this->n && $this->w[$i] <= $cleft) { $cleft -= $this->w[$i]; $b += $this->p[$i]; $i++; } if($i <= $this->n) { $b += $this->d[$i] * $cleft; } return $b; } function display() { foreach($this->st as $k) $r[] = array( 'w' => $this->w[$k], 'v' => $this->p[$k]); return $r; }} $ar=array(array(1,3),array(3,2),array(4,8),array(9,1),array(11,7),array(3,12),array(9,8),array(7,3));//值1表示重量，值2表示价格
$w=10;
$a=array();
$b=array();
$c=array();
for($i=0;$i
$a[$i]=$ar[$i][0];//重量数组
$b[$i]=$ar[$i][1]/$ar[$i][0]; //价格与重量比值数组
}
}
//print_r($a);
//print_r($b);
arsort($b);
$sum=0;
foreach($b as $key=>$value){
$sum=$sum+$a[$key];
if($sum>$w){break;};
$c[]=$ar[$key];
}
print_r($c);
//开始工作$w = 20;$arrWeight = array(9, 8, 2, 5, 7);$arrValue = array(12, 10, 7, 11, 3);$arr = array_combine($arrWeight, $arrValue);arsort($arr);$_w = 0;$arrSelect = array();//开始筛选foreach($arr as $key=>$val) { $_w += $key; if($_w <= $w) { $arrSelect[$key] = $val; }else { $_w -= $key; //这里用到了回溯 }}print_r($arrSelect);
$sw = 15; //背包重量为23$a = array(2, 3, 44, 5, 15, 12); //价值$w = array(5, 5, 8, 10, 3, 7); //重量//键名对应上价值跟重量$count = count($w);$k = 0;$m=0;for ($i = 0; $i < $count; $i++) { for ($s = 1; $s < $count; $s++) { //$s 为步长 $sumw[$k] = $w[$i]; //总重量 $suma[$k] = $a[$i]; //总价值 $road[$k][] = $i; //保存路径 for ($m = 0; $m < $count; $m++) { for ($j = $s; $j < $count; $j ++ ) { if (in_array($j,$road[$k])) { continue; } $sumw[$k] +=$w[$j]; if ($sumw[$k] <= $sw) { $road[$k][] = $j; $suma[$k]+=$a[$j]; } else { break; } } } $k++; }}arsort($suma);$max = current($suma);$r = array_keys($suma, $max);echo "MAX:" . $max . "<BR>";//输出路径：重量数组的键名$rr = 1;foreach ($r as $v) { echo "ROAD" . $rr . ": " . implode(',', $road[$v]) . "<BR>"; $rr++;} MAX:59
ROAD1: 2,4
ROAD2: 4,2
输出结果为
其他的均没有考虑步长的问题，而且重量相同，价值不同的情况也没有过滤
唠叨老大没看出来吗，一楼用的是穷举法，所有的组合先统计出来，然后一项项去比对
可以这么说， 就是穷举法，
因为所有方案中， 可能有m个不同的方案， 但他们的重量和价值比例是相同的，
不把所有子集的项遍历一次， 除非， 只挑一个方案， 就打印结果，
还有， 将质量和价值合并成一个数组的那些答案， 看下面，
//情况一$w = array(2, 8, 2, 5, 7); //质量$v = array(12, 10, 7, 11, 3); //价值$arr = array_combine($w, $v);//$arr 结果Array( [2] => 7 [8] => 10 [5] => 11 [7] => 3)//情况二$w = array(2, 2, 2, 2, 2);$v = array(12, 14, 7, 11, 3);$arr = array_combine($w, $v);Array( [2] => 3)
#16 楼的答案 $p = new Backtracking(array_values($w), array_values($v), 11);$p->parse();echo $p->BestValue();$p->display();//情况一 $w = array(2, 2, 2, 2, 7); //质量$v = array(12, 10, 4, 11, 3); //价值//结果40Array( [0] => Array ( [w] => 2 [v] => 12 ) [1] => Array ( [w] => 2 [v] => 11 ) [2] => Array ( [w] => 2 [v] => 10 ) [3] => Array ( [w] => 2 [v] => 4 ))//情况二$w = array(2, 8, 3, 2, 7); //质量$v = array(12, 10, 7, 11, 3); //价值//结果30Array( [0] => Array ( [w] => 2 [v] => 12 ) [1] => Array ( [w] => 2 [v] => 11 ) [2] => Array ( [w] => 3 [v] => 7 ) [3] => Array ( [w] => 8 [v] => 10 ))
我#16的代码已更新
经多组数据测试，我#16的代码得到的构成有问题
待解决后再参与讨论
$v = array(2, 4, 6, 8, 10);
$w = array(1, 2, 3, 4, 5);
$v = array(1, 2, 3, 4, 5);
$w = array(2, 4, 6, 8, 10);
若要用价值和质量 并成比例去计算的， 要排除这二种情况。
$ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2'=>'9','12'=>'8','9'=>'12','10'=>'15','15'=>'6');
$a=array();
$w=10;//所需重量
foreach($ar as $key=>$value){
if($key<=$w){$a[$key]=$value;}
}
//print_r($a);
foreach($a as $key=>$value){
$a[$key]=$value/$key;
}
arsort($a);
//print_r($a);
$sum=0;
$b=array();
foreach($a as $key=>$value){
$sum=$sum+$key;
if($sum>$w){break;};
$b[$key]=$ar[$key];
}
print_r($b);
$ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2'=>'9','12'=>'8','9'=>'12','10'=>'15','15'=>'6');
$a=array();
$w=10;//所需重量
foreach($ar as $key=>$value){
if($key<=$w){$a[$key]=$value;}
}
//pri……
明显不行，而且忘记考虑如果重量一样，价值又一样时候的选择
比如，所需重量是$w=10;
array('2'=>'5','2'=>'5','2'=>'5','2'=>'5','2'=>'5','5'=>'15','5'=>'10','8'=>'15','8'=>'10');
明显('2'=>'5','2'=>'5','2'=>'5','2'=>'5','2'=>'5')与('5'=>'15','5'=>'10')是一样的
把这个放到你的程序里得到
$ar=array('2'=>'5','2'=>'5','2'=>'5','2'=>'5','2'=>'5','5'=>'15','5'=>'10','8'=>'15','8'=>'10');
$a=array();
$w=10;//所需重量
foreach($ar as $key=>$value){
if($key<=$w){$a[$key]=$value;}
}
//print_r($a);
foreach($a as $key=>$value){
$a[$key]=$value/$key;
}
arsort($a);
//print_r($a);
$sum=0;
$b=array();
foreach($a as $key=>$value){
$sum=$sum+$key;
if($sum>$w){break;};
$b[$key]=$ar[$key];
}
print_r($b);
?>
得到结果是 Array ( [2] => 5 [5] => 10 )
PHP code
$sw = 15; //背包重量为23
$a = array(2, 3, 44, 5, 15, 12); //价值
$w = array(5, 5, 8, 10, 3, 7); //重量
//键名对应上价值跟重量
$count = count($w);
$k = 0;
$m=0;
for ($i = 0; $i < $count; $i++) {
……
你的代码也不行
$ar=array(array(1,3),array(3,2),array(4,8),array(9,1),array(11,7),array(3,12),array(9,8),array(7,3));//值1表示重量，值2表示价格
$w=10;
$a=array();
$b=array();
$c=array();
for($i=0;$i
<?php$ar=array(array(2,5),array(2,5),array(2,5),array(2,5),array(2,5),array(5,10),array(5,14),array(7,3));//值1表示重量，值2表示价格$w=10;$a=array();$b=array();$c=array();for($i=0;$i<count($ar);$i++){ if($ar[$i][0]<=$w){ $a[$i]=$ar[$i][0];//重量数组 $b[$i]=$ar[$i][1]/$ar[$i][0]; //价格与重量比值数组 }}//print_r($a);//print_r($b);arsort($b);$sum=0;foreach($b as $key=>$value){ $sum=$sum+$a[$key]; if($sum>$w){break;}; $c[]=$ar[$key];}print_r($c);?> 为便于测试结果，先发一个枚举的。
$bk = 15; //背包$a = array(2, 3, 44, 5, 15, 12); //价值$w = array(5, 5, 8, 10, 3, 7); //重量Knapsack($w, $a, $bk);function Knapsack($w, $a, $bk) { $k = array_keys($w); $r = array(); for($i=1; $i<=count($k); $i++) { $r = array_merge($r, combination($k, $i)); } foreach($r as $i=>$t) { $n = 0; $v = 0; foreach($t as $p) { $n += $w[$p]; $v += $a[$p]; } if($n > $bk) unset($r[$i]); else { $mv[$i] = $v; $mw[$i] = $n; } } array_multisort($mw, SORT_DESC, $mv, SORT_DESC, $r); foreach($mw as $i=>$v) { echo "w:$v v:{$mv[$i]} ["; foreach($r[$i] as $k) echo "({$w[$k]},{$a[$k]})"; echo "]\n"; }}
Solution to Connection reset
Which version of linux system is easy to use?
Why the computer keeps restarting automatically
Can Douyin short videos be restored after being deleted?
what is world wide web
How to solve the computer prompt of insufficient memory
What does the metaverse concept mean?
Usage of instr function in oracle
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
