有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<count($res); $p++) { $r = $res[$p]; foreach($ar as $i=>$v) { if(in_array($i, $res[$p]['k'])) continue; if($r['w'] + $v['w'] <= $w) { $res[] = array( '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']<1.1*$f;}));
太强了,感谢版主大人!非常牛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); //规格化
我这个算法并未完全按照动态规划去做
而是记录了所有可能的组合,最后用排序做检查
太感谢了,多谢您的指教

PHP主要是过程式编程,但也支持面向对象编程(OOP);Python支持多种范式,包括OOP、函数式和过程式编程。PHP适合web开发,Python适用于多种应用,如数据分析和机器学习。

PHP起源于1994年,由RasmusLerdorf开发,最初用于跟踪网站访问者,逐渐演变为服务器端脚本语言,广泛应用于网页开发。Python由GuidovanRossum于1980年代末开发,1991年首次发布,强调代码可读性和简洁性,适用于科学计算、数据分析等领域。

PHP适合网页开发和快速原型开发,Python适用于数据科学和机器学习。1.PHP用于动态网页开发,语法简单,适合快速开发。2.Python语法简洁,适用于多领域,库生态系统强大。

PHP在现代化进程中仍然重要,因为它支持大量网站和应用,并通过框架适应开发需求。1.PHP7提升了性能并引入了新功能。2.现代框架如Laravel、Symfony和CodeIgniter简化开发,提高代码质量。3.性能优化和最佳实践进一步提升应用效率。

PHPhassignificantlyimpactedwebdevelopmentandextendsbeyondit.1)ItpowersmajorplatformslikeWordPressandexcelsindatabaseinteractions.2)PHP'sadaptabilityallowsittoscaleforlargeapplicationsusingframeworkslikeLaravel.3)Beyondweb,PHPisusedincommand-linescrip

PHP类型提示提升代码质量和可读性。1)标量类型提示:自PHP7.0起,允许在函数参数中指定基本数据类型,如int、float等。2)返回类型提示:确保函数返回值类型的一致性。3)联合类型提示:自PHP8.0起,允许在函数参数或返回值中指定多个类型。4)可空类型提示:允许包含null值,处理可能返回空值的函数。

PHP中使用clone关键字创建对象副本,并通过\_\_clone魔法方法定制克隆行为。1.使用clone关键字进行浅拷贝,克隆对象的属性但不克隆对象属性内的对象。2.通过\_\_clone方法可以深拷贝嵌套对象,避免浅拷贝问题。3.注意避免克隆中的循环引用和性能问题,优化克隆操作以提高效率。

PHP适用于Web开发和内容管理系统,Python适合数据科学、机器学习和自动化脚本。1.PHP在构建快速、可扩展的网站和应用程序方面表现出色,常用于WordPress等CMS。2.Python在数据科学和机器学习领域表现卓越,拥有丰富的库如NumPy和TensorFlow。


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

Dreamweaver Mac版
视觉化网页开发工具

PhpStorm Mac 版本
最新(2018.2.1 )专业的PHP集成开发工具

螳螂BT
Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。

适用于 Eclipse 的 SAP NetWeaver 服务器适配器
将Eclipse与SAP NetWeaver应用服务器集成。

WebStorm Mac版
好用的JavaScript开发工具