背包dp——多重背包【小明的背包3】

记录一道关于背包dp的题目，多重背包综合了01背包和完全背包，让我们一起来看看吧~

文章目录

背包dp——多重背包【小明的背包3】
题目
题解
总结

题目

小明有一个容量为 V 的背包。
这天他去商场购物，商场一共有 N 种物品，第 i 种物品的体积为 wi ，价值为 vi ，数量为 si。
小明想知道在购买的物品总体积不超过 V的情况下所能获得的最大价值为多少，请你帮他算算。
**输入描述：
输入第 1 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。
第2∼N+1 行包含 3 个正整数 w,v,s，表示物品的体积和价值。
1<N≤10^2, 1<V<2 ×10^2, 1 ≤wi, vi,Si ≤ 2× 10^2。
**输出描述：
输出一行整数表示小明所能获得的最大价值。
**输入输出样例
示例：
**输入
3 30
1 2 3
4 5 6
7 8 9
**输出
39
运行限制
最大运行时间：1s
最大运行内存: 256M

题解

解题思路：
由于每个物品的总数量 * 总体积不确定，所以我们必须对对每个物品进行单独分析：
对于当前分析的该种物品，如果其（数量*体积）>（背包的总容量），则当做完全背包来处理，
否则，
将该物品的进行二进制拆分，（二进制优化的大概思想是：一个数可以拆分为多个”2的某次方” + “一个常数c”，通过组合这些拆分出来的数，同样可以在dp的过程中组合出所有的可能数，这就避免了从1~n这样去枚举每一种情况，从而降低时间复杂度），将拆分出的不同数量的同种物品看作为一种新物品，然后将这种新物品按01背包的方式进行处理（这里用的是降维的01背包，即滚动数组）。
代码如下（Java）：

import java.io.*;

public class Main {
    static int N = 1005;
    static int M = 2005;
    static int n, m;
    static int[] dp = new int[M];
    static int[] w = new int[N];
    static int[] v = new int[N];
    static int[] num = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] firstLine = br.readLine().split(" ");
        m = Integer.parseInt(firstLine[0]);
        n = Integer.parseInt(firstLine[1]);
        for (int i = 1; i <= m; i++) {
            String[] nextLine = br.readLine().split(" ");
            w[i] = Integer.parseInt(nextLine[0]);
            v[i] = Integer.parseInt(nextLine[1]);
            num[i] = Integer.parseInt(nextLine[2]);
        }
        for (int i = 1; i <= m; i++)
            MultiplePack(w[i], v[i], num[i]);
        System.out.println(dp[n]);
    }

    static void MultiplePack(int weight, int value, int number) {
        if (number * weight > n) CompletePack(weight, value);
        else {
            int k = 1;
            while (k <= number) {
                ZeroOnePack(k * weight, k * value);
                number -= k;
                k = k << 2;
            }
            if (number != 0) ZeroOnePack(number * weight, number * value);
        }
    }

    static void ZeroOnePack(int weight, int value) {
        for (int i = n; i >= weight; i--)
            dp[i] = Math.max(dp[i], dp[i - weight] + value);
    }

    static void CompletePack(int weight, int value) {
        for (int i = weight; i <= n; i++)
            dp[i] = Math.max(dp[i], dp[i - weight] + value);
    }

}