public class BagProblem_0_1 {
    int[] weight;
    int[] profit;
    int max_vol;
    public void setWeight(int[] weight) {
        this.weight = weight;
    }

    public void setProfit(int[] profit) {
        this.profit = profit;
    }

    public void setMax_vol(int max_vol) {
        this.max_vol = max_vol;
    }

    int[][] best_profit;

    public void solve(){
        if(weight.length!=profit.length){
            System.err.println("物品和价值的数目不匹配，请修正");
            return;
        }
        //创建表示最佳装配方案的数组，显然行数应该和物品数一样，列数应该和最大容量一样
        best_profit = new int[weight.length][max_vol+1];
        //java的数组被创建出来的时候会自动初始化为全零，因此不用刻意赋初始值
        //i表示需要考虑的物品的范围，注意0处是弃置不用的
        for(int i=1;i<weight.length;i++){
            //j表示允许使用的空间，当前状态下是装不下这个物品的
            for(int j=0;j<weight[i];j++){
                best_profit[i][j] = best_profit[i-1][j];
            }
            //此时可以装下，当前的最佳方案就在与不装之间选择，其中，如果决定要装，则将 【当前物品的价值】 加上 【在不考虑这个物品，且没有为它分配空间时】 的最大价值，就是当前条件下的最大价值
            for(int j=weight[i];j<=max_vol;j++){
                best_profit[i][j] = Math.max( best_profit[i-1][j] , profit[i] + best_profit[i-1][j-weight[i]]);
            }
        }
    }
    

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<weight.length;i++){
            for(int j=0;j<=max_vol;j++){
                sb.append(best_profit[i][j]).append(' ');
            }
            sb.append('\n');
        }
        sb.append('\n').append("最优解：").append(best_profit[weight.length-1][max_vol]);
        return sb.toString();
    }

    public static void main(String[] args) {
        BagProblem_0_1 bp = new BagProblem_0_1();
        int[] weight = {0,2,3,4,5};
        int[] profit = {0,3,4,5,6};
        bp.setWeight(weight);
        bp.setProfit(profit);
        bp.setMax_vol(14);
        bp.solve();
        System.out.println(bp);
    }
}