01背包问题Java

import java.util.Scanner;

public class Memoized_Knapsack {
    /*
     * 01背包问题
     * 
     * T: 背包容量v[]:价值数组 w[]:重量数组 c[][]:c[i][j]表示前 i 个物品在背包容量为 j 的情况下最优装包方案所能获得的最大价值
     * 
     * 输入： 物品数量 背包容量 \n 物品重量 物品价值 （有几个物品就输入几次本行）\n
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // N个物品
        int T = scanner.nextInt(); // 背包容量为T
        int[] w = new int[N]; // 重量数组，w[0] = 物品0号的重量
        int[] v = new int[N]; // 价值数组，v[0] = 物品0号的价值
        // 物品的重量、价值数组进行赋值
        for (int i = 0; i < N; i++) {
            w[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
        }
        int result = calculateMaxValue(w, v, N, T);
        System.out.println("最大价值为：" + result);
        scanner.close();
    }

    // 计算所能容纳的最大价值
    public static int calculateMaxValue(int[] w, int[] v, int N, int T) {
        int[][] c = new int[N][T + 1]; // 最大价值数组，物品编号0~(N-1)，容量0~T
        // 初始化最大价值数组c[][]
        for (int i = 0; i < N; i++) { // i为当前物品编号
            for (int j = 0; j < T + 1; j++) { // j为当前最大容量
                if (i == 0) {
                    if (w[0] <= j)
                        c[i][j] = v[0]; // 当0号物品的重量小于等于最大容量时，背包可以装下0号物品
                    else
                        c[i][j] = 0; // 背包装不下0号物品

                    continue;
                }
                if (j == 0)
                    c[i][j] = 0; // 背包容量为0时，什么也装不下
                /* 其他正经的情况 */
                if (j < w[i]) { // 物品i独占整个背包都装不下，所以就变成了“前i-1个物品在容量为j的最大价值”问题
                    c[i][j] = c[i - 1][j];
                } else { // 容量大于等于物品i的重量。分两种情况考虑：物品i只有装与不装两种状态
                    int v1 = c[i - 1][j - w[i]] + v[i]; // 物品i必定装进背包，此时的最大价值
                    /* 注：（上条代码）
                     * 因为本情况下i是必定要放进背包的，所以该结果就相当于：去掉物品i(所占的资源)后此时的最大价值 + 物品i的价值
                     *  c[i - 1][j - w[i]]代表的是：物品列表和最大容量两者都去除物品i所占的份额，此时i-1个物品在容量为j-w[i]情况下的最大价值
                     *  v[i]就是代表物品i的价值了
                     * 
                     * 至于为什么要减去w[i]而不是减去j，是因为物品i是要放进去的，所以要减去物品i所占用的重量份额，这样后面再加v[i]才合理
                     */
                    int v2 = c[i - 1][j]; // 物品i不装进背包，此时的最大价值
                    c[i][j] = Math.max(v1, v2); // 挑出两种状态中最大的价值s
                }
            }
        }
        printC(c);
        return c[N - 1][T];
    }

    public static void printC(int[][] c) {
        for (int i = 0; i < c.length; i++) {
            for (int j = 0; j < c[0].length; j++) {
                if (j == c[0].length - 1)
                    System.out.println(c[i][j]);
                else
                    System.out.print(c[i][j] + " ");
            }
        }
    }

}

• 分类： 默认分类 Java
• 标签： 01背包问题 背包问题 Java 算法