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

    //物品数量
    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];

    /**
     * dp[n][j] = 0
     *
     * if(j < WArray[i]){
     *     dp[i][j] = dp[i+1][j]
     * }else{
     *     dp[i][j] = max(dp[i+1][j], dp[i+1][j-WArray[i]]+VArray[i])
     * }
     */
    public void solution(){
        for(int i = n - 1; i >= 0; i--){
            for (int j = 0; j <= W; j++) {
                if(j < WArray[i]){
                    dp[i][j] = dp[i+1][j];
                }else{
                    dp[i][j] = Math.max(dp[i+1][j], dp[i+1][j-WArray[i]]+VArray[i]);
                }
            }
        }
        System.out.println(dp[0][5]);
    }

}