登录  /  注册
首页 > php教程 > PHP源码 > 正文

php实现贪心算法0-1背包问题

PHP中文网
发布: 2016-05-25 17:07:19
原创
2346人浏览过

1. [代码]希望高手用其它算法来实现0-1背包    

//0-1背包贪心算法问题
class tanxin{
	public $weight;
	public $price;
	public function __construct($weight=0,$price=0)
	{
		$this->weight=$weight;
		$this->price=$price;
	}
}
//生成数据
$n=10;
for($i=1;$i<=$n;$i++){
	$weight=rand(1,20);
	$price=rand(1,10);
	$x[$i]=new tanxin($weight,$price);
}
//输出结果
function display($x)
{
	$len=count($x);
	foreach($x as $val){
		echo $val->weight,&#39;  &#39;,$val->price;
		echo &#39;<br>&#39;;
	}
}
//按照价格和重量比排序
function tsort(&$x)
{
	$len=count($x);
	for($i=1;$i<=$len;$i++)
	{
		for($j=1;$j<=$len-$i;$j++)
		{	
			$temp=$x[$j];
			$res=$x[$j+1]->price/$x[$j+1]->weight;
			$temres=$temp->price/$temp->weight;
			if($res>$temres){
				$x[$j]=$x[$j+1];
				$x[$j+1]=$temp;
			}
		}
	}	
}
//贪心算法
function tanxin($x,$totalweight=50)
{
	$len=count($x);
	$allprice=0;
	for($i=1;$i<=$len;$i++){
		if($x[$i]->weight>$totalweight) break;
		else{
			$allprice+=$x[$i]->price;
			$totalweight=$totalweight-$x[$i]->weight;
		}
	}
	if($i<$len) $allprice+=$x[$i]->price*($totalweight/$x[$i]->weight);
	return $allprice;
}

tsort($x);//按非递增次序排序
display($x);//显示
echo &#39;0-1背包最优解为:&#39;;
echo tanxin($x);
登录后复制

                   

                   

智能AI问答
PHP中文网智能助手能迅速回答你的编程问题,提供实时的代码和解决方案,帮助你解决各种难题。不仅如此,它还能提供编程资源和学习指导,帮助你快速提升编程技能。无论你是初学者还是专业人士,AI智能助手都能成为你的可靠助手,助力你在编程领域取得更大的成就。
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
作者最新文章
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号