01背包问题-动态规划

时间：2022-11-17 18:44:11

背包问题是一个经典的动态规划模型，容易描述，容易理解。背包问题可简单描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。01背包问题的特点是，每种物品仅有一件，可以选择放或不放。

01背包问题描述：

　　有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

写出状态转移方程：

　　f[i][v]=max{f[i-1][v], f[i-1][v-c[i]]+w[i]}

f[i][v]:  前i件物品恰放入一个容量为v的背包可以获得的最大价值

f[i-1][v]:  前i-1件物品……（同上），即不放入第i件物品的情况

f[i-1][v-c[i]]+w[i]:  放入第i件物品的情况，放入后的 f[i][v] 应该等于前 i-1 件物品在容量为 v-c[i] 上的最大价值加上 w[i]

空间优化：

　　f[i][v]=max{f[i-1][v], f[i-1][v-c[i]]+w[i]}

　　观察黑色字体部分，发现二维数组完全可以用一维数组替代：

　　f[v]=max{f[v], f[v-c[i]]+w[i]}

程序怎么写？循环如何写？

　　首先考虑如果所有的物品都能放进去，那一定就是最大价值，如果只能放进去 i （i<N）件物品，那一定要选择一个最优策略，这个策略的结果是价值最大，而每个 i 的最优策略实际上又是基于 i-1 的最优策略的。根据分析写出如下循环

　　for(i=0; i<N; ++i)

　　　　for(v=V; v>w[i]; --v)  //逆序推能够保证 f[v-c[i]] 保存的是状态是 f[i-1][v-c[i]] ，也就是每个物品只被使用了一次；顺序的话 f[v-c[i]] 保存的是 f[i][v-c[i]] ，每个物品有可能被使用多次，也就是完全背包问题的解法。

　　　　　　f[v]=max(f[v], f[v-c[i]]+w[i])



题目1 : 01背包

时间限制: 20000ms
单点时限: 1000ms
内存限制: 256MB

描述

且说上一周的故事里，小Hi和小Ho费劲心思终于拿到了茫茫多的奖券！而现在，终于到了小Ho领取奖励的时刻了！

小Ho现在手上有M张奖券，而奖品区有N件奖品，分别标号为1到N，其中第i件奖品需要need(i)张奖券进行兑换，同时也只能兑换一次，为了使得辛苦得到的奖券不白白浪费，小Ho给每件奖品都评了分，其中第i件奖品的评分值为value(i),表示他对这件奖品的喜好值。现在他想知道，凭借他手上的这些奖券，可以换到哪些奖品，使得这些奖品的喜好值之和能够最大。

提示一：合理抽象问题、定义状态是动态规划最关键的一步

提示二：说过了减少时间消耗，我们再来看看如何减少空间消耗

输入

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第一行为两个正整数N和M,表示奖品的个数，以及小Ho手中的奖券数。

接下来的n行描述每一行描述一个奖品，其中第i行为两个整数need(i)和value(i)，意义如前文所述。

测试数据保证

对于100%的数据，N的值不超过500，M的值不超过10^5

对于100%的数据，need(i)不超过2*10^5, value(i)不超过10^3

输出

对于每组测试数据，输出一个整数Ans，表示小Ho可以获得的总喜好值。

样例输入 
5 1000
144 990
487 436
210 673
567 58
1056 897
样例输出 
2099
题解：主要是前i-1件物品的总价值，与第i件物品的比较，f[j]=max{f[j], f[j-w[i]]+v[i]};
AC code:
[cpp] view plain copy
  1. #include <iostream>  
  2. using namespace std;  
  3.   
  4. int main()  
  5. {  
  6.     int i,j,n,m;    
  7.     int w[505],v[505],bag[100050]={0};   
  8. //  memset(bag,0,sizeof(bag));  
  9.     cin>>n>>m;  
  10.     for(i=1; i<=n; i++)  
  11.       cin>>w[i]>>v[i];  
  12.     for(i=1; i<=n; i++)  
  13.     {  
  14.         for(j=m; j>=w[i]; j--)  
  15.         {  
  16.             if(bag[j-w[i]]+v[i]>bag[j])  
  17.             {  
  18.                  bag[j] = bag[j-w[i]]+v[i];  
  19.             }  
  20.         }  
  21.     }  
  22.     cout<<bag[m]<<endl;  
  23.   
  24.     return 0;  
  25. }  
Charm Bracelet
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 23433   Accepted: 10559

Description

Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weightWi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

Input

* Line 1: Two space-separated integers: N and M * Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di

Output

* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

Sample Input

4 6
1 4
2 6
3 12
2 7

Sample Output

23
ACcode:
<div class="dp-highlighter bg_cpp" style="font-family: Consolas, 'Courier New', Courier, mono, serif; font-size: 12px; width: 866.25px; overflow: auto; padding-top: 1px; margin: 18px 0px !important; background-color: rgb(231, 229, 220);"><div class="bar" style="padding-left: 45px;"><div class="tools" style="padding: 3px 8px 10px 10px; font-size: 9px; line-height: normal; font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; color: silver; border-left-width: 3px; border-left-style: solid; border-left-color: rgb(108, 226, 108); background-color: rgb(248, 248, 248);"><strong>[cpp]</strong> <a target=_blank href="http://blog.csdn.net/zxdfc/article/details/38536841#" class="ViewSource" title="view plain" style="color: rgb(160, 160, 160); text-decoration: none; border: none; padding: 1px; margin: 0px 10px 0px 0px; font-size: 9px; display: inline-block; width: 16px; height: 16px; text-indent: -2000px; background-image: url(http://static.blog.csdn.net/scripts/SyntaxHighlighter/styles/images/default/ico_plain.gif); background-attachment: initial; background-color: inherit; background-size: initial; background-origin: initial; background-clip: initial; background-position: 0% 0%; background-repeat: no-repeat;">view plain</a><a target=_blank href="http://blog.csdn.net/zxdfc/article/details/38536841#" class="CopyToClipboard" title="copy" style="color: rgb(160, 160, 160); text-decoration: none; border: none; padding: 1px; margin: 0px 10px 0px 0px; font-size: 9px; display: inline-block; width: 16px; height: 16px; text-indent: -2000px; background-image: url(http://static.blog.csdn.net/scripts/SyntaxHighlighter/styles/images/default/ico_copy.gif); background-attachment: initial; background-color: inherit; background-size: initial; background-origin: initial; background-clip: initial; background-position: 0% 0%; background-repeat: no-repeat;">copy</a><div style="position: absolute; left: 469px; top: 3327px; width: 18px; height: 18px; z-index: 99;"></div></div></div><ol start="1" class="dp-cpp" style="padding: 0px; border: none; list-style-position: initial; list-style-image: initial; color: rgb(92, 92, 92); margin: 0px 0px 1px 45px !important; background-color: rgb(255, 255, 255);"><li class="alt" style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; color: inherit; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important;"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;"><span class="preprocessor" style="margin: 0px; padding: 0px; border: none; color: gray; background-color: inherit;">#include <iostream></span><span style="margin: 0px; padding: 0px; border: none; background-color: inherit;">  </span></span></li><li style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important; background-color: rgb(248, 248, 248);"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;"><span class="keyword" style="margin: 0px; padding: 0px; border: none; color: rgb(0, 102, 153); font-weight: bold; background-color: inherit;">using</span><span style="margin: 0px; padding: 0px; border: none; background-color: inherit;"> </span><span class="keyword" style="margin: 0px; padding: 0px; border: none; color: rgb(0, 102, 153); font-weight: bold; background-color: inherit;">namespace</span><span style="margin: 0px; padding: 0px; border: none; background-color: inherit;"> std;  </span></span></li><li class="alt" style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; color: inherit; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important;"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;"><span class="datatypes" style="margin: 0px; padding: 0px; border: none; color: rgb(46, 139, 87); font-weight: bold; background-color: inherit;">int</span><span style="margin: 0px; padding: 0px; border: none; background-color: inherit;"> w[3403],v[3403],bag[100050];   </span></span></li><li style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important; background-color: rgb(248, 248, 248);"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;"><span class="datatypes" style="margin: 0px; padding: 0px; border: none; color: rgb(46, 139, 87); font-weight: bold; background-color: inherit;">int</span><span style="margin: 0px; padding: 0px; border: none; background-color: inherit;"> main()  </span></span></li><li class="alt" style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; color: inherit; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important;"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">{  </span></li><li style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important; background-color: rgb(248, 248, 248);"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">    <span class="datatypes" style="margin: 0px; padding: 0px; border: none; color: rgb(46, 139, 87); font-weight: bold; background-color: inherit;">int</span><span style="margin: 0px; padding: 0px; border: none; background-color: inherit;"> i,j,n,m;    </span></span></li><li class="alt" style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; color: inherit; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important;"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">      </span></li><li style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important; background-color: rgb(248, 248, 248);"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">  </span></li><li class="alt" style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; color: inherit; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important;"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">        cin>>n>>m;    </span></li><li style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important; background-color: rgb(248, 248, 248);"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">        <span class="keyword" style="margin: 0px; padding: 0px; border: none; color: rgb(0, 102, 153); font-weight: bold; background-color: inherit;">for</span><span style="margin: 0px; padding: 0px; border: none; background-color: inherit;">(i=0; i<n; ++i)  </span></span></li><li class="alt" style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; color: inherit; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important;"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">            cin>>w[i]>>v[i];  </span></li><li style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important; background-color: rgb(248, 248, 248);"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">        <span class="keyword" style="margin: 0px; padding: 0px; border: none; color: rgb(0, 102, 153); font-weight: bold; background-color: inherit;">for</span><span style="margin: 0px; padding: 0px; border: none; background-color: inherit;">(i=0; i<n; ++i)  </span></span></li><li class="alt" style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; color: inherit; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important;"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">        {  </span></li><li style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important; background-color: rgb(248, 248, 248);"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">            <span class="keyword" style="margin: 0px; padding: 0px; border: none; color: rgb(0, 102, 153); font-weight: bold; background-color: inherit;">for</span><span style="margin: 0px; padding: 0px; border: none; background-color: inherit;">(j=m; j>=w[i]; --j)  </span></span></li><li class="alt" style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; color: inherit; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important;"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">            {  </span></li><li style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important; background-color: rgb(248, 248, 248);"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">                <span class="keyword" style="margin: 0px; padding: 0px; border: none; color: rgb(0, 102, 153); font-weight: bold; background-color: inherit;">if</span><span style="margin: 0px; padding: 0px; border: none; background-color: inherit;">(bag[j-w[i]]+v[i]>bag[j])  </span></span></li><li class="alt" style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; color: inherit; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important;"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">                {  </span></li><li style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important; background-color: rgb(248, 248, 248);"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">                    bag[j] = bag[j-w[i]]+v[i];  </span></li><li class="alt" style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; color: inherit; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important;"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">                }  </span></li><li style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important; background-color: rgb(248, 248, 248);"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">            }  </span></li><li class="alt" style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; color: inherit; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important;"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">        }  </span></li><li style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important; background-color: rgb(248, 248, 248);"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">        cout<<bag[m]<<endl;  </span></li><li class="alt" style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; color: inherit; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important;"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">  </span></li><li style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important; background-color: rgb(248, 248, 248);"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">    <span class="keyword" style="margin: 0px; padding: 0px; border: none; color: rgb(0, 102, 153); font-weight: bold; background-color: inherit;">return</span><span style="margin: 0px; padding: 0px; border: none; background-color: inherit;"> 0;  </span></span></li><li class="alt" style="border-style: none none none solid; border-left-width: 3px; border-left-color: rgb(108, 226, 108); list-style: decimal-leading-zero outside; color: inherit; line-height: 18px; margin: 0px !important; padding: 0px 3px 0px 10px !important;"><span style="margin: 0px; padding: 0px; border: none; color: black; background-color: inherit;">}  </span></li><li></li></ol></div>
标签：

相关文章