​/*
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)的最大价值。
total(5,35)=total(4,35),不选第5个物品
total(5,35)=total(4,20)+v5,选时

(

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

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

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

以下直观理解
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;
}