01背包问题—Java代码

一、问题
描述

给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi。

问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

话不多说直接上代码

import java.util.Scanner;

public class bag01 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int max = sc.nextInt();
        
        // 重量
        int[] hight = new int[num+1];
        // 钱
        int[] money = new int[num+1];
        //输入重量
        for (int i = 1; i <= num; i++) {
            hight[i] = sc.nextInt();
        }
        //输入重量
        for (int i = 1; i <= num; i++) {
            money[i] = sc.nextInt();
        }
        //创建num+1个背包，背包能承受的重量为max（0不包括，从1 开始）
        int[][] arr = new int[num + 1][max + 1];
        
        //arr[0]第一个背包什么都不装所以不遍历（全为0）;
        for (int i = 1; i <= num; i++) {
            for (int j = 1; j <= max; j++) {
                //当前共有i个物品
                //如果当前的背包承受重量 j 大于第 i 个物品的重量，
                if (i > 0 && hight[i] <= j) {
                //那么对比上一个背包的当前背包承受重量的最大值 和 上一个背包减去当前 i 物品的重量hight[i]，并加上 i 物品的价值money[i]，
                //就相当于把上个背包承受重量减去 i 的重量，这样就刚刚能塞下 i 物品，
                //因为塞下 i 物品，所以在加上 i 物品的重量。
                //添加 i 物品和不添加 i 物品的价值对比。    
                    if(arr[i - 1][j] > (arr[i - 1][j - hight[i]] + money[i])) {
                        //如果不添加i物品的价值最大的话，那么当前的背包数量等于不添加物品的价值
                        arr[i][j] = arr[i - 1][j];
                    }else {
                        //如果添加 i 物品的价值大的话那么当前j背包数量的价值就等于添加i物品后的价值。
                        arr[i][j] = arr[i - 1][j - hight[i]] + money[i];
                    }   
                    /*arr[i][j] = (arr[i - 1][j] > (arr[i - 1][j - money[i]] + hight[i]) ? arr[i - 1][j]
                            : arr[i - 1][j - money[i]] + hight[i]);*/
                } else {
                //如果当前背包装不下i物品那么当前背包价值等于上一个背包当前重量的价值。
                    arr[i][j] = arr[i - 1][j];
                }
                /**
                 * 输出一行背包
                 */
                //System.out.print(arr[i][j]+"   ");
            }
            /**
             * 控制台输出换行
             */
            //System.out.println();
        }
    }
}