/**
 * 有n个重量和价值分别为Wi,Vi的物品。
 * 从这些物品中挑选出总重量不超过W的物品，求所有有挑选方案中价值总和的最大值
 * @author haofan.whf
 * @version $Id: Bag01.java, v 0.1 2018年06月14日 下午7:26 haofan.whf Exp $
 */
public class Bag01 {

    //物品数量
    int n = 4;

    //背包容量
    int W = 5;

    //物品重量
    int[] WArray = new int[]{2,1,3,2};

    //物品价值
    int[] VArray = new int[]{3,2,4,2};

    //用数组来存储已经被计算过的值，用来剪枝
    int[][] dp = new int[n+1][W+1];
    
    {
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                dp[i][j] = -1;
            }
        }
    }

    //从第i个物品开始挑选总重量<j的部分
    public int solution(int i, int j){
        //当已经得知计算的结果时，直接返回
        if(dp[i][j] >= 0){
            return dp[i][j];
        }
        int res = 0;
        if(i == n){
            //已经没有剩余的物品了
            res = 0;
        }else if(j < WArray[i]){
            //当前物品放不下，移至下一个物品
            res = solution(i + 1, j);
        }else{
            //如果能放下则放/不放两种场景都需要计算，并取得最大值
            res = Math.max(solution(i + 1, j - WArray[i]) + VArray[i]
                    , solution(i + 1,j));
        }
        dp[i][j] = res;
        return res;
    }
}