关于多重背包优化问题的思考

第一步：明确优化目标

第二步：确定优化时导致改变或消失的条件

第三步：划分条件改变后f[i][j]的变化并确定优化方案

由此可以看出无法使用完全背包问题的方式来优化，因此我们选择以二进制计数的方式将多重背包问题转化为01背包问题

java代码：

朴素版（多重背包问题I）：

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        String[] a1 = in.readLine().split(" ");
        int n = Integer.parseInt(a1[0]);
        int m = Integer.parseInt(a1[1]);

        int[][] f = new int[n + 1][m + 1];
        int[] v = new int[n + 1];
        int[] w = new int[n + 1];
        int[] s = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            String[] a2 = in.readLine().split(" ");
            v[i] = Integer.parseInt(a2[0]);
            w[i] = Integer.parseInt(a2[1]);
            s[i] = Integer.parseInt(a2[2]);
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k * v[i] <= j && k <= s[i]; k++) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
                }
            }
        }

        System.out.print(f[n][m]);

        in.close();
    }
}

优化k层循环版（多重背包问题II）：

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        String[] a1 = in.readLine().split(" ");
        int n = Integer.parseInt(a1[0]);
        int m = Integer.parseInt(a1[1]);

        //最大是s[i]为2000 --> 2的11次方
        int[][] f = new int[n * 12][m + 1];
        int[] v = new int[n * 12];
        int[] w = new int[n * 12];

        int cnt = 0;

        for (int i = 1; i <= n; i++) {
            int k = 1;

            String[] a2 = in.readLine().split(" ");
            int a = Integer.parseInt(a2[0]);
            int b = Integer.parseInt(a2[1]);
            int s = Integer.parseInt(a2[2]);

            while (k <= s) {
                cnt++;
                v[cnt] = a * k;
                w[cnt] = b * k;
                s -= k;
                k *= 2;
            }

            if (s > 0) {
                cnt++;
                v[cnt] = a * s;
                w[cnt] = b * s;
            }
        }

        n = cnt;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                f[i][j] = f[i -1][j];
                if (j >= v[i]) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i]] + w[i]);
                }
            }
        }

        System.out.print(f[n][m]);

        in.close();
    }
}

优化数组维度（终极版多重背包问题II）：

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        String[] a1 = in.readLine().split(" ");
        int n = Integer.parseInt(a1[0]);
        int m = Integer.parseInt(a1[1]);

        int[] f = new int[m + 1];
        int[] v = new int[n * 12];
        int[] w = new int[n * 12];

        int cnt = 0;

        for (int i = 1; i <= n; i++) {
            int k = 1;

            String[] a2 = in.readLine().split(" ");
            int a = Integer.parseInt(a2[0]);
            int b = Integer.parseInt(a2[1]);
            int s = Integer.parseInt(a2[2]);

            while (k <= s) {
                cnt++;
                v[cnt] = a * k;
                w[cnt] = b * k;
                s -= k;
                k *= 2;
            }

            if (s > 0) {
                cnt++;
                v[cnt] = a * s;
                w[cnt] = b * s;
            }
        }

        n = cnt;

        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= v[i]; j--) {
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
            }
        }

        System.out.print(f[m]);

        in.close();
    }
}