题目
小明有一个容量为 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); } }
总结
背包问题是动态规划的一种常见考法，我们不仅要学会01和完全背包，还要灵活运用，来解决多重背包的问题。
文章粗浅，希望对大家有帮助！
