欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

请教各位大神一个变形的背包问题

程序员文章站 2023-12-24 21:14:46
...
有N种物品和一个容量为V的背包。还有一个阈值T。
第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和大于且最接近T。

附完全背包代码

/**
*背包问题描述:一个承受最大重量为W的背包,现在有n个物品,每个物品重量为t, 每个物品的价值为v。
* 要使得这个背包重量最大(但不能超过W),同时又需要背包的价值最大。
*思路:定义一个二维数组,一维为物品数量(表示每个物品),二维是重量(不超过最大,这里是10),下面数组a,
*动态规划原理思想,max(opt(i-1,w),wi+opt(i-1,w-wi)) 当中最大值,
*opt(i-1,w-wi)指上一个最优解
*/
//这是我根据动态规划原理写的
// max(opt(i-1,w),wi+opt(i-1,w-wi))
//背包可以装最大的重量
$w=10;
//这里有四件物品,每件物品的重量
$dx=array(3,4,5);
//每件物品的价值
$qz=array(4,5,6);
//定义一个数组
$a=array();
//初始化
for($i=0;$i for ($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=10
if($dx[$j-1] if(!isset($a[$j-1][$i-$dx[$j-1]])) continue;
//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]." ";
} echo "
";
}


?>


回复讨论(解决方案)

你遇到了什么问题呢?你的结果应该是对的
不过我喜欢这么写

$w = 10;$ar = array(  array('w' => 3, 'v' => 4),  array('w' => 4, 'v' => 5),  array('w' => 5, 'v' => 6),);foreach($ar as $k=>$v) {  $v['k'][] = $k;  $res[] = $v;}$p = 0;for(;$p$v) {    if(in_array($i, $res[$p]['k'])) continue;    if($r['w'] + $v['w']  $r['w'] + $v['w'],        'v' => $r['v'] + $v['v'],        'k' => array_merge($r['k'], array($i)),      );    }  }}foreach($res as $v) $t[] = $v['v'];array_multisort($t, SORT_DESC, $res); print_r($res);
Array(    [0] => Array        (            [w] => 9            [v] => 11            [k] => Array                (                    [0] => 1                    [1] => 2                )        )    [1] => Array        (            [w] => 9            [v] => 11            [k] => Array                (                    [0] => 2                    [1] => 1                )        )    [2] => Array        (            [w] => 8            [v] => 10            [k] => Array                (                    [0] => 0                    [1] => 2                )        )    [3] => Array        (            [w] => 8            [v] => 10            [k] => Array                (                    [0] => 2                    [1] => 0                )        )    [4] => Array        (            [w] => 7            [v] => 9            [k] => Array                (                    [0] => 0                    [1] => 1                )        )    [5] => Array        (            [w] => 7            [v] => 9            [k] => Array                (                    [0] => 1                    [1] => 0                )        )    [6] => Array        (            [w] => 5            [v] => 6            [k] => Array                (                    [0] => 2                )        )    [7] => Array        (            [w] => 4            [v] => 5            [k] => Array                (                    [0] => 1                )        )    [8] => Array        (            [w] => 3            [v] => 4            [k] => Array                (                    [0] => 0                )        ))

目前这个是 装满了w=10的背包的最大价值。

我是想找出:在尽量装满背包的情况下,总价值接近给定的一个阈值T 的组合

$f = 9;print_r(array_filter($res, function($a) use ($f) { return $a['v'] > 0.9*$f && $a['v']  


太强了,感谢版主大人!非常牛B,结果完全达到了

这个算法你写的太简洁了,有点看不懂,再请教您一下,怎么过滤掉重复的组合啊? 比如 0 3 6 ,3 0 6,6 0 3

....array_multisort($t, SORT_DESC, $res); //排序(已有的)foreach($res as $i=>$v) if(isset($res[$i-1]) && ! array_diff($res[$i-1]['k'], $v['k'])) unset($res[$i]); //去重$res = array_values($res); //规格化


我这个算法并未完全按照动态规划去做
而是记录了所有可能的组合,最后用排序做检查

太感谢了,多谢您的指教

上一篇:

下一篇: