本帖最后由 xuzuning 于 2011-06-10 14:40:16 编辑
给定物品n件,他们的重量分别是w[0],w[1],……w[n-1],物品的价值分别为v[0],v[1],……v[n-1],另有一个背包,它可以容纳的总重量为w。设计一种物品挑选方案,要求从这n件物品中所选取的物品的总重量不超过背包的容量w,使选中物品的价值之和最大。
这个是很常见的背包回溯算法,谁能用php写一下!
注意:与算法无关的回复,将毫不留情的删去! 版主
这个是很常见的背包回溯算法,谁能用php写一下!
注意:与算法无关的回复,将毫不留情的删去! 版主
分享到:
------解决方案--------------------
这个题至少要一个小时, 我说思路, 让别人做吧。
1. 对w的数组排序, 选出小于w重量的项(赋值数组p),
2. 对p数组计算笛卡尔积乘积阵列,选出所有子集里的项的和小于w重量的子集(赋值数组r),
3. 对r数组里的每个子集里的项转换成相对应的v值, 并分别求和(赋值数组wv),
4. 对wv数组排序, 得出对大的值的键就是结果。
------解决方案--------------------
------解决方案--------------------
------解决方案--------------------
这个题至少要一个小时, 我说思路, 让别人做吧。
1. 对w的数组排序, 选出小于w重量的项(赋值数组p),
2. 对p数组计算笛卡尔积乘积阵列,选出所有子集里的项的和小于w重量的子集(赋值数组r),
3. 对r数组里的每个子集里的项转换成相对应的v值, 并分别求和(赋值数组wv),
4. 对wv数组排序, 得出对大的值的键就是结果。
------解决方案--------------------
$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 "";";
print_r($_r);
echo "
?>
------解决方案--------------------
本帖最后由 xuzuning 于 2011-06-10 14:01:34 编辑
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;声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。相关文章推荐
• 聊聊php怎么让Swoole/Pool进程池实现Redis持久连接• 一文解析PHP元转分的错误示范(附代码实例)• PHP+Socket系列之实现websocket聊天室• PHP+Socket系列之IO多路复用及实现web服务器• PHP+Socket系列之实现客户端与服务端数据传输
相关课程推荐
PHP入门视频教程之一周学会PHP
所有计算机语言的学习都要从基础开始,《PHP入门视频教程之一周学会PHP》不仅是PHP的基础部分更主要的是PHP语言的核心技术,是学习PHP必须掌握的内容,任何PHP项目的实现都离不开这部分的内容,通过一周的深入学习让你快速掌握PHP的各项技能,助你的工作和学习更上层楼!
PHP教程245809次播放
弹指间学会HTML视频教程
《弹指间学会HTML视频教程》从最基本的概念开始讲起,步步深入,带领大家学习HTML,了解各种常用标签的意义以及基本用法,学习HTML知识为以后的学习打下基础
HTML教程70502次播放
弹指间学会CSS视频教程
CSS即层叠样式表(Cascading StyleSheet)。 在网页制作时采用层叠样式表技术,可以有效地对页面的布局、字体、颜色、背景和其它效果实现更加精确的控制。
CSS教程43554次播放
CSS3 最新视频教程
《CSS3 最新视频教程》中 CSS 用于控制网页的样式和布局。 CSS3 是最新的 CSS 标准, 本教程向您讲解 CSS3 中的新特性。通过实例进行讲解,更容易提高学习的效率!
CSS3教程30490次播放
1/1