📄 knapsackproblem.htm
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>背包问题（Knapsack Problem）</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 背包问题（Knapsack Problem）</a></h1>
<h2> 说明</h2>
假设有一个背包的负重最多可达8公斤，而希望在背包中装入负重范围内可得之总价物品，假设是水果好了，水果的编号、单价与重量如下所示： <br>
<table border="1" width="50%">
<tbody>
<tr>
<td align="left" valign="top"><small>0 </small></td>
<td align="left" valign="top"><small>李子 </small></td>
<td align="left" valign="top"><small>4KG </small></td>
<td align="left" valign="top"><small>NT$4500 </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>1 </small></td>
<td align="left" valign="top"><small>苹果 </small></td>
<td align="left" valign="top"><small>5KG </small></td>
<td align="left" valign="top"><small>NT$5700 </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>2 </small></td>
<td align="left" valign="top"><small>橘子 </small></td>
<td align="left" valign="top"><small>2KG </small></td>
<td align="left" valign="top"><small>NT$2250 </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>3 </small></td>
<td align="left" valign="top"><small>草莓 </small></td>
<td align="left" valign="top"><small>1KG </small></td>
<td align="left" valign="top"><small>NT$1100 </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>4 </small></td>
<td align="left" valign="top"><small>甜瓜 </small></td>
<td align="left" valign="top"><small>6KG </small></td>
<td align="left" valign="top"><small>NT$6700 </small></td>
</tr>
</tbody>
</table>
<p></p>
<h2> 解法</h2>
背包问题是关于最佳化的问题，要解最佳化问题可以使用“动态规划”（Dynamic
programming），从空集合开始，每增加一个元素就先求出该阶段的最佳解，直到所有的元素加入至集合中，最后得到的就是最佳解。 <br>
<br>
以背包问题为例，我们使用两个阵列value与item，value表示目前的最佳解所得之总价，item表示最后一个放至背包的水果，假设有负重量
1～8的背包8个，并对每个背包求其最佳解。 <br>
<br>
逐步将水果放入背包中，并求该阶段的最佳解：<br>
<ul>
<li> 放入李子
</li>
</ul>
<table border="1" width="50%">
<tbody>
<tr>
<td align="left" valign="top"><small>背包负重 </small></td>
<td align="left" valign="top"><small>1 </small></td>
<td align="left" valign="top"><small>2 </small></td>
<td align="left" valign="top"><small>3 </small></td>
<td align="left" valign="top"><small>4 </small></td>
<td align="left" valign="top"><small>5 </small></td>
<td align="left" valign="top"><small>6 </small></td>
<td align="left" valign="top"><small>7 </small></td>
<td align="left" valign="top"><small>8 </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>value </small></td>
<td align="left" valign="top"><small>０ </small></td>
<td align="left" valign="top"><small>０ </small></td>
<td align="left" valign="top"><small>０ </small></td>
<td align="left" valign="top"><small>4500 </small></td>
<td align="left" valign="top"><small>4500 </small></td>
<td align="left" valign="top"><small>4500 </small></td>
<td align="left" valign="top"><small>4500 </small></td>
<td align="left" valign="top"><small>9000 </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>item </small></td>
<td align="left" valign="top"><small>－ </small></td>
<td align="left" valign="top"><small>－ </small></td>
<td align="left" valign="top"><small>－ </small></td>
<td align="left" valign="top"><small>０ </small></td>
<td align="left" valign="top"><small>０ </small></td>
<td align="left" valign="top"><small>０ </small></td>
<td align="left" valign="top"><small>０ </small></td>
<td align="left" valign="top"><small>０ </small></td>
</tr>
</tbody>
</table>
<br>
<ul>
<li> 放入苹果
</li>
</ul>
<table border="1" width="50%">
<tbody>
<tr>
<td align="left" valign="top"><small>背包负重 </small></td>
<td align="left" valign="top"><small>1 </small></td>
<td align="left" valign="top"><small>2 </small></td>
<td align="left" valign="top"><small>3 </small></td>
<td align="left" valign="top"><small>4 </small></td>
<td align="left" valign="top"><small>5 </small></td>
<td align="left" valign="top"><small>6 </small></td>
<td align="left" valign="top"><small>7 </small></td>
<td align="left" valign="top"><small>8 </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>value </small></td>
<td align="left" valign="top"><small>０ </small></td>
<td align="left" valign="top"><small>０ </small></td>
<td align="left" valign="top"><small>０ </small></td>
<td align="left" valign="top"><small>4500 </small></td>
<td align="left" valign="top"><small>5700 </small></td>
<td align="left" valign="top"><small>5700 </small></td>
<td align="left" valign="top"><small>5700 </small></td>
<td align="left" valign="top"><small>9000 </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>item </small></td>
<td align="left" valign="top"><small>－ </small></td>
<td align="left" valign="top"><small>－ </small></td>
<td align="left" valign="top"><small>－ </small></td>
<td align="left" valign="top"><small>０ </small></td>
<td align="left" valign="top"><small>1 </small></td>
<td align="left" valign="top"><small>1 </small></td>
<td align="left" valign="top"><small>1 </small></td>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -