01背包学习

数据结构及算法 | 2013-06-20 20:41:19 | 阅读 1445 次 | 评论(0)

01背包动态规划思维不同于常规思维,需要学习前人的研究成果,但只要认真,看下百度百科,掌握了方法及参数的内容,基本上就差不多了,动态转移方程的理解熟悉后其实就能直接理解。
通过实例学习,
序號(i) 單個物重量w(i) 單個物品價值v(i)
1 22 15
2 18 18
3 9 10
4 24 13
5 15 20
包能承最大重35

求total(5,35)的最大价值。

1,怎樣理解 total( i,j)?我們把它看成函數,它的值就是從 i個物品中選,總重量不超j的所选物品的最大价值。

i參數 是從前 i 個物品選,其中不一定遷中。 j參數是此時背包能承的最大重量。

如果选了一個物品 i,則剩下的空間承重為 j-W( i)

2,构造树 (见附表 不会做图,,效果不好)

A:從頂開始,如 total( 5,35),不遷第5個物品,背包能承重仍為35,作為左子樹

total( 4,35)。

B: 遷第5個物品時,此時背包還能承的重量為(35-15),剩下的物品在不包含第5個物品中遷。此時函 数轉化為total( 4,20)作為右子樹。

  重復A,B后,得此題的樹,最后底層函數值全為0。

這其實是一遞歸過程,完成后再從底往上計算,每個父結點的值為:(右子樹值加上父結點第I個物品價值, 與左子樹比較,哪個大就作為該父結點的值。

此反復可很方便得出頂根結點的值 total(5,35)=38。

把A,B抽象:     ***total(i,j)***  根                 

    total(i-1,j)左子树;    total(i-1 , j-w(i))右子树, 加上V(i)          

以上就是背包問題的狀態轉移方程理解過程。

#include <stdio.h>

int w[5]={22,18,9,24,15};
int v[5]={15,18,10,13,20};
int total(int i,int j)
{
int l,r,t;
if(i==-1||j==0) return 0;
if(w[i]>j ) return total(i-1,j);
if(w[i]<=j ) {l=total(i-1,j);r=v[i]+total(i-1,j-w[i]);t=l>r?l:r;}
return t;
}
int main()
{

printf("total(5,35)=%d\n",total(5,35));
return 0;

}

{QFW4JCZHVMI7RC~07Y[`@X.jpg (上传于2013-06-20 20:41:19)
{QFW4JCZHVMI7RC~07Y[`@X.jpg
文章评论,共0条
游客请输入验证码
浏览176862次
最新评论
  • zhouwenyuan:博主可以开发房产APP吗?
  • qunxingw:结合附件,在分表A或B...实验一下宏就理解了
  • qunxingw:这仅是小范围的一种思路,此题是指数级的数据。