final int w_count=10; int v_count=0; int w[]=new int[]{4,5,1,3,2}; int v[]=new int[]{8,3,9,7,10}; Arrays.sort(w); Arrays.sort(v); int weight=0; for(int i=0 ;i<w.length;i++){ if ((weight + w[i]) > w_count){ break ; } weight+=i; v_count+=v[i]; } System.out.print("最大值为: "+v_count); 楼主 这种算法还是蛮简单的
2. 对p数组计算笛卡尔积乘积阵列,选出所有子集里的项的和小于w重量的子集(赋值数组r),
3. 对r数组里的每个子集里的项转换成相对应的v值, 并分别求和(赋值数组wv),
4. 对wv数组排序, 得出对大的值的键就是结果。
-----------------------------
就是对子集项求和, 如
{1,3,5} --> (1+3+5) < w
{2,6} --> (2+6) < w
$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);
<?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>";
print_r($_r);
echo "</pre>";
?>
$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);
$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++;
}以为我写的代码,测试过是可以的实现的,不理解的,可以提问
ROAD1: 2,4
ROAD2: 4,2输出结果为
$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
)Array
(
[2] => 3
)
$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); //价值//结果
30
Array
(
[0] => Array
(
[w] => 2
[v] => 12
) [1] => Array
(
[w] => 2
[v] => 11
) [2] => Array
(
[w] => 3
[v] => 7
) [3] => Array
(
[w] => 8
[v] => 10
))
$w = array(1, 2, 3, 4, 5); $v = array(1, 2, 3, 4, 5);
$w = array(2, 4, 6, 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);
比如,所需重量是$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')是一样的把这个放到你的程序里得到
<?php$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$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);
?>
输出为Array ( [0] => Array ( [0] => 5 [1] => 14 ) [1] => Array ( [0] => 2 [1] => 5 ) [2] => Array ( [0] => 2 [1] => 5 ) )是错误的结果标准答案应该是Array ( [0] => Array ( [0] => 2 [1] => 5 ) [1] => Array ( [0] => 2 [1] => 5 ) [2] => Array ( [0] => 2 [1] => 5 ) [3] => Array ( [0] => 2 [1] => 5 )[4] => Array ( [0] => 2 [1] => 5 ))
static $ret = array();
if($m == 0) {
$m = count($ar);
$ret = array();
}
for($i=$m; $i>=$k; $i--) {
$a[$k-1] = $ar[$i-1];
if($k > 1) {
combination(&$ar, $k-1, $i-1, $a);
}else {
array_unshift ($ret, array_reverse($a));
}
}
return $ret;
}
class BagPlanning
{
private $containment = 0;//背包容量
private $quantity = 0;//物品数
private $weight = array();//物品重量数组
private $price = array();//物品价值数组
private $result = array(); private $max_result = 0;//最佳结果
private $max_ids = array();//获取最佳结果的物品选择方式 function __construct($containment, $weight, $price)
{
$this->containment = $containment;
$this->weight = $weight;
$this->price = $price;
$this->quantity = count($this->weight);
$this->result = array_fill(0, $this->quantity + 1, array_fill(0, $this->containment + 1, array('best_result' => 0, 'ids' => array())));
$this->bag_planning();
echo join(',', $this->max_ids), '=', $this->max_result;
} public function bag_planning()
{
for($i=1;$i<=$this->quantity;++$i)
{
for($j=1;$j<=$this->containment;++$j)
{
if($this->weight[$i-1] <= $j)
{
if($this->price[$i-1] + $this->result[$i-1][$j-$this->weight[$i-1]]['best_result'] > $this->result[$i-1][$j]['best_result'])
{
$this->result[$i][$j]['best_result'] = $this->price[$i-1] + $this->result[$i-1][$j-$this->weight[$i-1]]['best_result'];
$this->result[$i][$j]['ids'] = array_merge($this->result[$i-1][$j-$this->weight[$i-1]]['ids'], array($i-1));
if($this->result[$i][$j]['best_result'] > $this->max_result)
{
$this->max_result = $this->result[$i][$j]['best_result'];
$this->max_ids = $this->result[$i][$j]['ids'];
}
}
else
{
$this->result[$i][$j] = $this->result[$i-1][$j-$this->weight[$i-1]];
}
}
else
{
$this->result[$i][$j] = $this->result[$i-1][$j];
}
}
}
}
}
$t = new BagPlanning(3, array(1, 2, 3), array(4, 5, 6));
0,1=9
這是一篇cpp的回溯算法,你可以借鉴一下他的编程思想来用php完成.
之前写过动态规划的,根据上面同学的测试样例,在同重不同价的数据源下发现有bug,趁这个帖子,改过下.
回溯/贪心法等有空再复习整理下。
<?php
$weight = array(2, 3, 44, 5, 15, 12);
$price = array(5, 5, 8, 17, 3, 7);
$limitw = 15;
echo "<pre/><br/>";
echo "物品重量<br/>".print_r($weight,1)."<br/>";
echo "对应价格<br/>".print_r($price,1)."<br/>";
echo "限制重量:".$limitw."<br/>========================================<br/>";
echo "不可重复放置同一物品的结果:<br/>";
print_r(bag01_dp($limitw,$weight,$price,false));
echo "可重复放置同一物品的结果:<br/>";
print_r(bag01_dp($limitw,$weight,$price,true));
/**
*@params
*$limitw -- 限重
*$weight -- 重量
*$price -- 价格
*$multiple -- true为可重复放置同一件物品,false表示每件物品只能放一次
*/
function bag01_dp($limitw,$weight,$price,$multiple)
{
$ps = $tp = array();
for($i = 0 ; $i <= $limitw ; $i++) :
foreach( $weight as $k=>$v) :
$o = $i -$v;
$li= $k-1;
$l = $weight[$li];
$lp = !$multiple ? $ps[$o][$l.$li] : max($ps[$o][$l.$li],$ps[$o][$v.$k]);
$lk = ($lp === $ps[$o][$l.$li]) ? $l.$li : $v.$k;
//当前物品重量 <= 当前背包最大承受重量
if( $v <= $i) :
//当前价格 + 剩余价格最优解 > 上次最优解
if( $price[$k] + $lp > $ps[$i][$l.$li]) :
$ps[$i][$v.$k] = $price[$k] + $lp;
$tp[$i][$v.$k] = $tp[$o][$lk];
$tp[$i][$v.$k][] = $v."(".$price[$k].")";
else :
$ps[$i][$v.$k] = $ps[$i][$l.$li];
$tp[$i][$v.$k] = $tp[$i][$lk];
endif;
else :
$ps[$i][$v.$k] = $ps[$i][$l.$li];
$tp[$i][$v.$k] = $tp[$i][$lk];
endif;
endforeach;
endfor;
return array('price'=>end(end($ps)),'items'=>end(end($tp)));
}
?>
他这个有点类似,
1.贪婪法
2.回溯法
3.动态规划
4.递归
都可以解的出来不过原理归原理,真的写起来你会发现要考虑的问题蛮多的,特别没有人用PHP写过看看这里这么多人写的,有几人可以用的
<?php
/**
*@description
*主要思想是,搜索一颗深度为n(n=物品数量)的树,符合限定条件的节点,将搜索左右子树,不符合的的节点,将只搜索左子树
*假设w[] = (2,3,4) p[] = (4,5,6),限重量为7,则最终搜索树应为
2
0/ \1
3 3
0/ \1 0/ \1
4 4 4 4
|1 |1 |1 |0
(4) (3,4) (2,4)(2,3) --- 最终可能解,只需判断物品价值最高的一组
*上图中0,1分别代表当前节点是否叠加/或\线上面的节点重量
*假设以上数据,限重变成了4,则最终搜索树应为
2
0/ \1
3 3 (因为3 + 2 > 4,所以只搜索左子树)
0/ \1 0/
4 4 4
|1 |0 |0
(4) (3) (2) --- 最终可能解,判断价值最高的一组
*/
class bag01_bt{
public $weight = array();//重量
public $price = array();//价格
public $limitw = 0; //限重
public $n = 0; //树的层级
public $x = array();//底层节点->根节点的叠加节点
public $cx = array();//是否叠加当前节点
public $cp = 0; //叠加节点的总价格
public $cw = 0; //叠加节点的总重量
public $bp = 0; //最优价格
public function bag01_bt($limitw,$weight,$price)
{
$this->n = count($weight);
$this->weight = $weight;
$this->price = $price;
$this->limitw = $limitw;
} public function backstracking( $n=0 )
{
if($n >= $this->n)
{
if($this->cp > $this->bp )
{
$this->bp = $this->cp;
$this->x = $this->cx;
}
return false;
}
//符合条件,记录当前节点为1,且叠加当前物品重量,继续搜索右子数
if($this->cw + $this->weight[$n] <= $this->limitw)
{
$this->cw += $this->weight[$n];
$this->cp += $this->price[$n];
$this->cx[$n] = 1;
$this->backstracking( $n + 1);
$this->cw -= $this->weight[$n];
$this->cp -= $this->price[$n];
}
//不记录当前节点,不叠加当前物品重量,搜索左子树
$this->cx[$n] = 0;
$this->backstracking( $n + 1);
}
}
$weight = array(2, 3, 44, 5, 15, 12);
$price = array(5, 5, 8, 17, 3, 7);
$limitw = 30;$bag = new bag01_bt($limitw,$weight,$price);
$bag->backstracking( );
echo "<pre/><br/>";
echo "最优解:";
echo $bag->bp."<br/>";
echo "物品:<br/>";
foreach($bag->x as $k=>$v)
{
if($v == 1) $items[] = $bag->weight[$k]."(".$bag->price[$k].")";
}
print_r($items);
?>
$price = array(3,7,6,4,10,32);
$limitw = 10;The height weight :10
Products:
Array
(
[0] => 3(3)
[1] => 7(7)
)
$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('3'=>'3'
,'7'=>'7'
,'4'=>'6'
,'6'=>'4'
,'10'=>'10'
,'12'=>'32'
,'5'=>'5');
$a=array();
$w=10;//所需重量
{
$arr1 = array (
'0' => array ('fid' => 1, 'tid' => 1, 'name' => 'Name1' ),
'1' => array ('fid' => 1, 'tid' => 2 , 'name' => 'Name2' ),
'2' => array ('fid' => 1, 'tid' => 5 , 'name' => 'Name3' ),
'3' => array ('fid' => 1, 'tid' => 7 , 'name' => 'Name4' ),
'4' => array ('fid' => 3, 'tid' => 9, 'name' => 'Name5' )
);
$arr2 = array();
foreach ($arr1 as $key => $value)
{
$arr2[$valuewww.overlookworld.com= array('tid' => $value['tid'],'name' => $value['name']);
}
return $arr2;
baidu一下背包问题就会有了,挺简单的。记得之前去暴风影音面试C++的时候笔试题的程序题中就有一题是背包问题要当时写出可运行程序。
function PackAri($maxweig, $weigs, $valus){
//$maxweig--最大承重
//$weigs--重量数组
//$valus--价值数组
//首先排除单个重量大于$maxweig的
foreach($weigs as $key => $value){
if($value > $maxweig){
unset($weigs[$key]);
unset($valus[$key]);
}
} //进行重量数组元素的排列组合
$weig_tmp = array();
$valu_tmp = array();
$weig_ret = array();
$valu_ret = array();
do{
$weig_tmp[] = array_pop($weigs);
$valu_tmp[] = array_pop($valus);
foreach($weig_tmp as $key => $value){ //左结合
$weig_ret[] = array_merge($weigs, array($value));
$valu_ret[] = array_merge($valus, array($valu_tmp[$key]));
}
foreach($weigs as $key => $value){ //右结合
$weig_ret[] = array_merge($weig_tmp, array($value));
$valu_ret[] = array_merge($valu_tmp, array($valus[$key]));
}
}while(count($weigs) > 1); //再次排除总重量大于规定的
foreach($weig_ret as $key => $value){
if(array_sum($value) > $maxweig){
unset($weig_ret[$key]);
unset($valu_ret[$key]);
}
} //选出最大价值的元素
$maxkey = key($valu_ret);
$maxval = array_sum(current($valu_ret));
while($value = current($valu_ret)){
$sum = array_sum($value);
if($sum > $maxval){
$maxval = $sum;
$maxkey = key($valu_ret);
}
next($valu_ret);
} //返回结果
if(isset($weig_ret)){
$result["weig"] = $weig_ret[$maxkey];
$result["valu"] = $valu_ret[$maxkey];
return $result;
}else return false;
}$m1 = 110;
$w1 = array(23, 34, 45, 56, 49, 230, 12, 446);
$v1 = array(25, 11, 34, 23, 65, 56, 23, 45);
$test1 = PackAri($m1, $w1, $v1);
var_dump($test1);$m2 = 30;
$w2 = array(2, 3, 44, 5, 15, 12);
$v2 = array(5, 5, 8, 17, 3, 7);
$test2 = PackAri($m2, $w2, $v2);
var_dump($test2);
总重量是W。
首先各物品按重量从小到大排序,w[0],w[1],...,w[i],...w[n]
其次,把物品重量大于W的去掉,即w[i]<=W,保留物品[0],w[1],...,w[i]
然后物品重量拆分W:
假定W=5,w[0]=1,w[1]=2,w[0]=3,w[3]=4
取法:
保留4,压入3,判断(4+3)>5,舍去3,压入2,判断(4+2)>5,舍去2,压入1,判断(4+1)!>5,保留1。取得第一组值4,1
保留3,压入2,判断(3+2)!>5,保留2,压入1,判断(3+2+1)>5,舍去1,取得第二组数据3,2
保留3,压入1,判断(3+1)!>5。取得第三组数据3,1
保留2,压入1,判断(2+1)!>5。取得第三组数据2,1拆分完毕之后再根据价值计算最大价值和
int v_count=0;
int w[]=new int[]{4,5,1,3,2};
int v[]=new int[]{8,3,9,7,10};
Arrays.sort(w);
Arrays.sort(v);
int weight=0;
for(int i=0 ;i<w.length;i++){
if ((weight + w[i]) > w_count){
break ;
}
weight+=i;
v_count+=v[i];
}
System.out.print("最大值为: "+v_count);
楼主 这种算法还是蛮简单的