package dp.背包01;

public class knapsack {
    /**
     * 01背包就是 往包里装东西，固定容量内最大价值
     *
     * 东西有俩个属性，体积和价值，背包有一个属性容量
     *
     * 每次装东西，n（第n个物品）,c（背包的容量）就会变化
     * @param n
     * @param c
     * @return
     */

    static int[] v = {0,2,4,3,7};
    static int[] w = {0,2,3,5,5};
    public static int knapsack(int n,int c){
        int[][] res =new int[n+1][c+1];
        for (int i = 0; i <=n; i++) {
            res[i][0] = 0;
       }

        for (int i = 0; i <= c; i++) {
            res[0][c]=0;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= c; j++) {
                if(j<w[i]){
                    res[i][j]=res[i-1][j];
                }else{
                    res[i][j] = Math.max(res[i-1][j],res[i-1][j-w[i-1]]+v[i]);
                }
            }
        }
        return res[n][c];
    }



    public static void main(String[] args) {
        System.out.println(knapsack(4,10));
    }
}