博客

当初年少，见识少，看过之后不理解，于是放弃了深入学习背包问题，现在见识有一些了，特此记录一下学习后写的模板（慢慢更新），原谅我的命名不规范（可拷贝下来自己改类名），主要是为了自己的区分。

一.01背包模板——Java实现

二.完全背包模板——Java实现

一.01背包_二维数组实现

import java.util.Scanner;

public class TwoChoicesOfBackpacks01背包_二维数组实现 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int V = input.nextInt();
        int[] value = new int[N];
        int[] weight = new int[N];
        for (int i = 0; i < N; i++) {
            weight[i] = input.nextInt();
            value[i] = input.nextInt();
        }
        int[][] backpacks = new int[N + 1][V + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= V; j++) {
                //此时在相的背包大小下如果放不下当前物品就看看以前在相同大小下方的物品和价值是多少
                backpacks[i][j] = backpacks[i - 1][j];
                if (j >= weight[i - 1]) {
                    //对比以前的同等背包大小的情况下的最大的价值和以前物品在当前背包容量-当前物品重量的背包大小的最大价值加上当前物品价值，选出最大值。
                    backpacks[i][j] = Math.max(backpacks[i - 1][j], backpacks[i - 1][j - weight[i - 1]] + value[i - 1]);
                }
            }
        }
        System.out.println(backpacks[N][V]);
    }
}

二.01背包_一维数组实现

我们通过计算中间值发现当我们决定放还是不放第i个物品的时候，所用到的中间值之和第i – 1个物品那一行的中间值有关，所以我们将空间进一步缩小优化。

import java.util.Scanner;

/**
 * 讲空间复杂度降低，由二维数组改为一维数组，不保存所有的中间值，只保留当前运算所需要用的值，同时采用背包大小倒序遍历，因为backpacks[j - weight[i - 1]]
 * 不采用倒序则会先更新前面的序列，导致我们使用的值backpacks[i][j - weight[i - 1]。
 * 输入数据：
 * 4 5
 * 1 2
 * 2 4
 * 3 4
 * 4 5
 * 中间计算的值：
 * 0 2 2 2 2 2
 * 0 2 4 6 6 6
 * 0 2 4 6 6 8
 * 0 2 4 6 6 8
 * 输出：
 * 8
 */
public class TwoChoicesOfBackpacks01背包_一维数组实现 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int V = input.nextInt();
        int[] value = new int[N];
        int[] weight = new int[N];
        for (int i = 0; i < N; i++) {
            weight[i] = input.nextInt();
            value[i] = input.nextInt();
        }
        int[] backpacks = new int[V + 1];
        for (int i = 0; i < N; i++) {
            for (int j = V; j >= weight[i]; j--)
                backpacks[j] = Math.max(backpacks[j], backpacks[j - weight[i]] + value[i]);
        }
        System.out.println(backpacks[V]);
    }
}

三.01背包_包满最大值

import java.util.Arrays;
import java.util.Scanner;

/**
 * 求刚好将背包装满的时候的物品价值，如果所有的物品都凑不齐，则输出背包无法装满，否则输出装满时候的最大的价值。
 * 输入数据：
 * 4 5
 * 1 2
 * 2 4
 * 3 4
 * 4 5
 * 中间计算的值：
 * 0 2 -1 -1 -1 -1
 * 0 2 4 6 -1 -1
 * 0 2 4 6 6 8
 * 0 2 4 6 6 8
 * 输出：
 * 8
 */
public class TwoChoicesOfBackpacks01背包_包满最大值 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int V = input.nextInt();
        int[] value = new int[N];
        int[] weight = new int[N];
        for (int i = 0; i < N; i++) {
            weight[i] = input.nextInt();
            value[i] = input.nextInt();
        }
        int[] backpacks = new int[V + 1];
        /**如果赋值为Integer.MIN_VALUE，则不需要进行if (backpacks[j - weight[i]] != Integer.MIN_VALUE)，这是因为
         * 在进行对比时，backpacks[j] = Math.max(backpacks[j], backpacks[j - weight[i]] + value[i]);会有一个
         * backpacks[j - weight[i]] + value[i]，此值永远是负值（前提是此值足够小于求得背包里物品的价值，最大值不会大于背包里物品价值的最小值，
         * 也就是0），与预期符合，如果使用一个比较小的值，比如-1，如果不进行if (backpacks[j - weight[i]] != -1)，
         * 造成backpacks[j - weight[i]] + value[i]值有可能大于backpacks[j]，此时结果不符合预期，所以不满足if条件，不参与运算。*/
        Arrays.fill(backpacks, 1, V + 1, -1);
        for (int i = 0; i < N; i++) {
            for (int j = V; j >= weight[i]; j--) {
                if (backpacks[j - weight[i]] != -1)
                    backpacks[j] = Math.max(backpacks[j], backpacks[j - weight[i]] + value[i]);
            }
        }
        if (backpacks[V] == -1)
            System.out.println("Backpack is not full");
        else
            System.out.println(backpacks[V]);
    }
}

四.01背包_包满最小值

import java.util.Arrays;
import java.util.Scanner;

/**
 * 输入数据：
 * 4 5
 * 1 2
 * 2 4
 * 3 4
 * 4 5
 * 中间计算的值：
 * 0 2 2147483647 2147483647 2147483647 2147483647
 * 0 2 4 6 2147483647 2147483647
 * 0 2 4 4 6 8
 * 0 2 4 4 5 7
 * 输出：
 * 7
 */
public class TwoChoicesOfBackpacks01背包_包满最小值 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int V = input.nextInt();
        int[] value = new int[N];
        int[] weight = new int[N];
        for (int i = 0; i < N; i++) {
            weight[i] = input.nextInt();
            value[i] = input.nextInt();
        }
        int[] backpacks = new int[V + 1];
        /**如果赋值为Integer.MAX_VALUE，则需要进行if (backpacks[j - weight[i]] != Integer.MAX_VALUE)，这是因为
         * 在进行对比时，backpacks[j] = Math.min(backpacks[j], backpacks[j - weight[i]] + value[i]);会有一个
         * backpacks[j - weight[i]] + value[i]，会造成溢出，成为负值，与预期不符合，如果使用一个比较大的值，比如1000000
         * （前提是此值足够大于求得背包里物品的价值），这样就不会溢出，结果符合预期*/
        Arrays.fill(backpacks, 1, V + 1, Integer.MAX_VALUE);
        for (int i = 0; i < N; i++) {
            for (int j = V; j >= weight[i]; j--) {
                if (backpacks[j - weight[i]] != Integer.MAX_VALUE)
                    backpacks[j] = Math.min(backpacks[j], backpacks[j - weight[i]] + value[i]);
            }
        }

        if (backpacks[V] == Integer.MAX_VALUE)
            System.out.println("Backpack is not full");
        else
            System.out.println(backpacks[V]);
    }
}

五.01背包优化——减少数据量

import java.util.Scanner;

/**
 * https://www.jianshu.com/p/8d41d87fcbb7
 * 此网址为优化的解释
 */
public class TwoChoicesOfBackpacks01背包_LargePackageCapacity {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int V = input.nextInt();
        int[] value = new int[N];
        int[] weight = new int[N];
        for (int i = 0; i < N; i++) {
            weight[i] = input.nextInt();
            value[i] = input.nextInt();
        }
        int[] backpacks = new int[V + 1];
        for (int i = 0; i < N; i++) {
            int sum = 0;
            for (int k = i + 1; k < N; k++) {
                sum += weight[k];
            }
            int tail = Math.max(V - sum, weight[i]);
            for (int j = V; j >= tail; j--)
                backpacks[j] = Math.max(backpacks[j], backpacks[j - weight[i]] + value[i]);
        }
        System.out.println(backpacks[V]);
    }
}

如果文中我的理解有偏差或者错误，请阅读者评论指出，不胜感激。