背包问题

0-1 背包问题

问题描述

• 给定n种物品和一个背包，物品i的重量是w_i，其价值为v_i，背包的容量为c，问应如何选择装入背包的中的物品，使得装入背包中的物品的总价值最大。
• 在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包，不能将物品i装入背包多次，也不能只装入部分的物品i

代码实现

流程图

public class Knapsack {

    public static void main(String[] args) {
        float[] w = {1, 3, 10, 5, 3, 5, 6, 8, 8, 3, 12};
        float[] v = {1, 2, 1, 5, 1, 5, 6, 2, 8, 200, 1};
        int n = w.length;
        Boolean[] x = new Boolean[n];
        float M = 30;
        Knapsack(n, M, v, w, x);
        for (int i = 0; i < n; i++) {
            System.out.printf("%3d: weight: %-6.2f load: %6b\n", i + 1, w[i], x[i]);
        }
    }

    public static void Knapsack(int n, float M, float[] v, float[] w, Boolean[] x) {
        int[] t = new int[n];
        float c = M;
        Sort(w, v, t, n);
        int i;
        for (i = 0; i < n; i++) {
            x[i] = false;
        }
        for (i = 0; i < n && w[t[i]] <= c; i++) {
            x[t[i]] = true;
            c -= w[t[i]];
        }
    }

    public static void Sort(float[] w, float[] v, int[] t, int n) {
        float[] array = new float[n];
        for (int i = 0; i < n; i++) {
            array[i] = v[i] / w[i];
        }
        float temp;
        int index;
        for (int i = 0; i < n; i++) {
            t[i] = i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] < array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;

                    index = t[j];
                    t[j] = t[j + 1];
                    t[j + 1] = index;
                }
            }
        }
    }
}

• Knapsack(int n, float M, float[] v, float[] w, Boolean[] x)：计算0-1背包问题。
  • int n：物品的数量。
  • float M：背包的最大载重量。
  • float[] v：每件物品的价值。
  • float[] w：每件物品的重量。
  • Boolean[] x：每件物品是否装入背包。
• Sort(float[] w, float[] v, int[] t, int n)：通过物品的价值重量比，由大到小进行排序。
  • float[] w：每件物品的重量。
  • float[] v：每件物品的价值。
  • int[] t：排序后数组的下标。
  • int n：物品的数量。

背包问题

问题描述

• 给定n种物品和一个背包，物品i的重量是w_i，其价值为v_i，背包的容量为c，问应如何选择装入背包的中的物品，使得装入背包中的物品的总价值最大。
• 在选择装入背包的物品时，不能将物品i装入背包多次，但是可以选择物品i的一部分，而不一定要全部装入背包。

代码实现

流程图

public class Knapsack {
    public static void main(String[] args) {
        float[] w = {1, 3, 10, 5, 3, 5, 6, 8, 8, 3, 12};
        float[] v = {1, 2, 1, 5, 1, 5, 6, 2, 8, 200, 1};
        int n = w.length;
        float[] x = new float[n];
        float M = 30;
        Knapsack(n, M, v, w, x);
        for (int i = 0; i < n; i++) {
            System.out.printf("%3d: weight: %-6.2f load: %6.2f%%\n", i + 1, w[i], x[i] * 100);
        }
    }

    public static void Knapsack(int n, float M, float[] v, float[] w, float[] x) {
        int[] t = new int[n];
        float c = M;
        Sort(w, v, t, n);
        int i;
        for (i = 0; i < n; i++) {
            x[i] = 0;
        }
        for (i = 0; i < n && w[t[i]] <= c; i++) {
            x[t[i]] = 1;
            c -= w[t[i]];
        }
        if (i <= n) {
            x[i] = c / w[t[i]];
        }
    }

    public static void Sort(float[] w, float[] v, int[] t, int n) {
        float[] array = new float[n];
        for (int i = 0; i < n; i++) {
            array[i] = v[i] / w[i];
        }
        float temp;
        int index;
        for (int i = 0; i < n; i++) {
            t[i] = i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] < array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;

                    index = t[j];
                    t[j] = t[j + 1];
                    t[j + 1] = index;
                }
            }
        }
    }
}

• Knapsack(int n, float M, float[] v, float[] w, float[] x)：计算0-1背包问题。
  • int n：物品的数量。
  • float M：背包的最大载重量。
  • float[] v：每件物品的价值。
  • float[] w：每件物品的重量。
  • float[] x：每件物品装入背包的占比。
• Sort(float[] w, float[] v, int[] t, int n)：通过物品的价值重量比，由大到小进行排序。
  • float[] w：每件物品的重量。
  • float[] v：每件物品的价值。
  • int[] t：排序后数组的下标。
  • int n：物品的数量。