这个是很常见的背包回溯算法,谁能用php写一下!
注意:与算法无关的回复,将毫不留情的删去! 版主
------解决方案--------------------
这个题至少要一个小时, 我说思路, 让别人做吧。
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 "
?>
------解决方案--------------------
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;php入门到就业线上直播课:查看学习
声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。前端(VUE)零基础到就业课程:点击学习
自己动手写 PHP MVC 框架:点击学习
相关文章推荐
• ❤️🔥共22门课程,总价3725元,会员免费学• ❤️🔥接口自动化测试不想写代码?• 4.与数据库的连接_PHP• 搜索引擎技术核心揭密• CodeIgniter框架过滤HTML危险代码_php实例• jquery 怎么获取fckeditor的内容• 异常求解 大神们
相关课程推荐
独孤九贱(3)_JavaScript视频教程
javascript是运行在浏览器上的脚本语言,连续多年,被评为全球最受欢迎的编程语言。是前端开发必备三大法器中,最具杀伤力。如果前端开发是降龙十八掌,好么javascript就是第18掌:亢龙有悔。没有它,你的前端生涯是不完整的。《php.cn独孤九贱(3)-JavaScript视频教程》课程特色:php中文网原创幽默段子系列课程,以恶搞,段子为主题风格的php视频教程!轻松的教学风格,简短的教学模式,让同学们在不知不觉中,学会了javascript知识。
JavaScript教程139518次播放
独孤九贱(6)_jQuery视频教程
jQuery是一个快速、简洁的JavaScript框架。设计的宗旨是“write Less,Do More”,即倡导写更少的代码,做更多的事情。它封装JavaScript常用的功能代码,提供一种简便的JavaScript设计模式,优化HTML文档操作、事件处理、动画设计和Ajax交互。 核心特性可以总结为:具有独特的链式语法和短小清晰的多功能接口;具有高效灵活的css选择器,并且可对CSS选择器进行扩展;拥有便捷的插件扩展机制和丰富的插件。兼容各种主流浏览器,如IE 6.0+、FF 1.5+、Safari 2.0+、Opera 9.0+等,是全球最流行的前端开发框架之一。PHP中文网根据最新版本,独家录制jQuery最新视频教程,回馈PHP中文网的新老用户。
jQuery教程114639次播放
jQuery与Ajax基础与实战
jQuery是最流行的JS函数库,封装了许多实用的功能,其中最引人入胜的就是Ajax。 jQuery中的Ajax操作,语法简单,操作方便,使Ajax从未如此轻松,前端人员从此不再为与服务器异步交互而发愁,本套课程,精选了最常用的几个方法,从基本的语法到每个参数,再到具体实例进行了全面的讲解。
AJAX教程14319次播放
Git教程(60分钟全程无废话版)
Git 是一个开源的分布式版本控制系统,用于敏捷高效地处理任何或小或大的项目。 Git 是 Linus Torvalds 为了帮助管理 Linux 内核开发而开发的一个开放源码的版本控制软件。 Git 与常用的版本控制工具 CVS, Subversion 等不同,它采用了分布式版本库的方式,不必服务器端软件支持
JavaScript教程12336次播放
workerman实战课1/1