请教各位大神一个变形的背包问题
有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); //规格化
我这个算法并未完全按照动态规划去做
而是记录了所有可能的组合,最后用排序做检查
太感谢了,多谢您的指教

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

Alipay PHP...

JWT is an open standard based on JSON, used to securely transmit information between parties, mainly for identity authentication and information exchange. 1. JWT consists of three parts: Header, Payload and Signature. 2. The working principle of JWT includes three steps: generating JWT, verifying JWT and parsing Payload. 3. When using JWT for authentication in PHP, JWT can be generated and verified, and user role and permission information can be included in advanced usage. 4. Common errors include signature verification failure, token expiration, and payload oversized. Debugging skills include using debugging tools and logging. 5. Performance optimization and best practices include using appropriate signature algorithms, setting validity periods reasonably,

Session hijacking can be achieved through the following steps: 1. Obtain the session ID, 2. Use the session ID, 3. Keep the session active. The methods to prevent session hijacking in PHP include: 1. Use the session_regenerate_id() function to regenerate the session ID, 2. Store session data through the database, 3. Ensure that all session data is transmitted through HTTPS.

How to debug CLI mode in PHPStorm? When developing with PHPStorm, sometimes we need to debug PHP in command line interface (CLI) mode...

The application of SOLID principle in PHP development includes: 1. Single responsibility principle (SRP): Each class is responsible for only one function. 2. Open and close principle (OCP): Changes are achieved through extension rather than modification. 3. Lisch's Substitution Principle (LSP): Subclasses can replace base classes without affecting program accuracy. 4. Interface isolation principle (ISP): Use fine-grained interfaces to avoid dependencies and unused methods. 5. Dependency inversion principle (DIP): High and low-level modules rely on abstraction and are implemented through dependency injection.

How to automatically set the permissions of unixsocket after the system restarts. Every time the system restarts, we need to execute the following command to modify the permissions of unixsocket: sudo...

Static binding (static::) implements late static binding (LSB) in PHP, allowing calling classes to be referenced in static contexts rather than defining classes. 1) The parsing process is performed at runtime, 2) Look up the call class in the inheritance relationship, 3) It may bring performance overhead.

Sending JSON data using PHP's cURL library In PHP development, it is often necessary to interact with external APIs. One of the common ways is to use cURL library to send POST�...
