<h2>01背包问题</h2>
<p> 给定n种物品，和一个容量为C的背包，物品i的重量是w[i],其价值为v[i]。问如何选择装入背包的物品，使得装入背包中的总价值最大？（面对每个武平，只能有选择拿取或者不拿两种选择，不能选择装入某物品的一部分，也不能装入物品多次）</p>
<ul>
<li>声明一个数组<code>f[n][c]</code>的二维数组，<code>f[i][j]</code>表示在面对第i件物品，且背包容量为j时所能获得的最大价值。</li>
<li>根据题目要求进行打表查找相关的边界和规律</li>
<li>根据打表列写相关的状态转移方程</li>
<li>用程序实现状态转移方程</li>
</ul>
<p><strong>真题演练：</strong></p>
<p> 一个旅行者有一个最多能装M公斤的背包，现在有n件物品，它们的重量分别是W1、W2、W3、W4、…、Wn。它们的价值分别是C1、C3、C2、…、Cn,求旅行者能获得最大价值。</p>
<p><strong>输入描述：</strong></p>
<p> 第一行：两个整数，M（背包容量，M<= 200)和N（物品数量，N<=30);<br>
第2…N+1行：每行两个整数Wi，Ci，表示每个物品的质量与价值。</p>
<p><strong>输出描述：</strong></p>
<p> 仅一行，一个数，表示最大总价值</p>
<p><strong>样例：</strong></p>
<blockquote>
<p>输入：<br>
10 4<br>
2 1<br>
3 3<br>
4 5<br>
7 9<br>
输出：<br>
12</p>
</blockquote>
<p><strong>解题步骤</strong></p>
<p>定义一个数组<code>dp[i][j]</code>表示容量为j时，拿第i个物品时所能获取的最大价值。</p>
<p>按照题目要求进行打表，列出对应的dp表。
<thead>
</thead>
<th align="center"></th>
</p>
<p>
<table>
<thead>
<tr>
<th>W[i]（质量）</th>
<th>V[i]（价值）</th>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
<th>7</th>
<th>8</th>
<th>9</th>
<th>10</th>
</tr>
</thead>
<tbody>
<tr>
<td></td>
<td></td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td>2</td>
<td>1</td>
<td>0</td>
<td>0</td>
<td><span style="color: #ff0000">1</span></td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
</tr>
<tr>
<td>3</td>
<td>3</td>
<td>0</td>
<td>0</td>
<td>1</td>
<td><span style="color: #ff0000">3</span></td>
<td>3</td>
<td>4</td>
<td>4</td>
<td>4</td>
<td>4</td>
<td>4</td>
<td>4</td>
</tr>
<tr>
<td>4</td>
<td>5</td>
<td>0</td>
<td>0</td>
<td>1</td>
<td>3</td>
<td>5</td>
<td>5</td>
<td>6</td>
<td>8</td>
<td>8</td>
<td>9</td>
<td>9</td>
</tr>
<tr>
<td>7</td>
<td>9</td>
<td>0</td>
<td>0</td>
<td>1</td>
<td>3</td>
<td>5</td>
<td>5</td>
<td>6</td>
<td>9</td>
<td>9</td>
<td>10</td>
<td>12</td>
</tr>
</tbody>
</table>
</p>
<p> 对于一个<code>动态规划问题设置下标时最好从0开始，因为动态规划经常会和上一个状态有关系</code>！从上面的dp表可以看出来对于一个物品我们拿还是不难需要进行两步来判断。<strong>第一步：判断背包当前的容量j是否大于物品当前的质量，如果物品的质量大于背包的容量那么就舍弃。第二步：如果背包可以装下这个物品，就需要判断装下该物品获取的最大价值是不是大于不装下这个物品所获取的最大价值，如果大于那么就把东西装下</strong>！根据这样的思想我们可以得到状态转移方程：</p>
<p>如果单签背包的容量可以装下物品:<br>
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);<br>
如果当前背包的容量装不下该物品:<br>
dp[i][j]=dp[i-1][j];<br>
</p>
<div class="blockcode">
<pre class="brush:cpp;">
#include <stdio.h>
int max(const int a,const int b)
{
return a>b ? a:b;
}
int main()
{
int w[35]={0},v[35]={0},dp[35][210]={0};
int n,m;
scanf("%d %d",&m,&n);
int i,j;
for(i=1;i<=n;i++){
scanf("%d %d",&w[i],&v[i]);
|
|
转播
