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;
}
