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

To protect the application from session-related XSS attacks, the following measures are required: 1. Set the HttpOnly and Secure flags to protect the session cookies. 2. Export codes for all user inputs. 3. Implement content security policy (CSP) to limit script sources. Through these policies, session-related XSS attacks can be effectively protected and user data can be ensured.

Methods to optimize PHP session performance include: 1. Delay session start, 2. Use database to store sessions, 3. Compress session data, 4. Manage session life cycle, and 5. Implement session sharing. These strategies can significantly improve the efficiency of applications in high concurrency environments.

Thesession.gc_maxlifetimesettinginPHPdeterminesthelifespanofsessiondata,setinseconds.1)It'sconfiguredinphp.iniorviaini_set().2)Abalanceisneededtoavoidperformanceissuesandunexpectedlogouts.3)PHP'sgarbagecollectionisprobabilistic,influencedbygc_probabi

In PHP, you can use the session_name() function to configure the session name. The specific steps are as follows: 1. Use the session_name() function to set the session name, such as session_name("my_session"). 2. After setting the session name, call session_start() to start the session. Configuring session names can avoid session data conflicts between multiple applications and enhance security, but pay attention to the uniqueness, security, length and setting timing of session names.

The session ID should be regenerated regularly at login, before sensitive operations, and every 30 minutes. 1. Regenerate the session ID when logging in to prevent session fixed attacks. 2. Regenerate before sensitive operations to improve safety. 3. Regular regeneration reduces long-term utilization risks, but the user experience needs to be weighed.

Setting session cookie parameters in PHP can be achieved through the session_set_cookie_params() function. 1) Use this function to set parameters, such as expiration time, path, domain name, security flag, etc.; 2) Call session_start() to make the parameters take effect; 3) Dynamically adjust parameters according to needs, such as user login status; 4) Pay attention to setting secure and httponly flags to improve security.

The main purpose of using sessions in PHP is to maintain the status of the user between different pages. 1) The session is started through the session_start() function, creating a unique session ID and storing it in the user cookie. 2) Session data is saved on the server, allowing data to be passed between different requests, such as login status and shopping cart content.

How to share a session between subdomains? Implemented by setting session cookies for common domain names. 1. Set the domain of the session cookie to .example.com on the server side. 2. Choose the appropriate session storage method, such as memory, database or distributed cache. 3. Pass the session ID through cookies, and the server retrieves and updates the session data based on the ID.


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

VSCode Windows 64-bit Download
A free and powerful IDE editor launched by Microsoft

MinGW - Minimalist GNU for Windows
This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

mPDF
mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

PhpStorm Mac version
The latest (2018.2.1) professional PHP integrated development tool

SublimeText3 English version
Recommended: Win version, supports code prompts!