19921 多重背包

⭐️难度：中等
🌟考点：动态规划、背包问题
📖

📚

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {static int N = 100010;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[] v = new int[2000*12]; // v w数组要开大一点，因为物品个数会增多，假如每个物品可以使用2000次int[] w = new int[2000*12]; // 总共有2000个物品，就要用2000 * log2(2000) ≈ 2000 * 12int[] dp = new int[200002];// 数据预处理int p = 1;for (int i = 1; i <= n; i++) {int V = sc.nextInt();int W = sc.nextInt();int C = sc.nextInt();int k = 1;while(C > k){v[p] = V * k;w[p] = W * k;C -= k;k *= 2;p++;}if(C > 0){v[p] = V * C;w[p] = W * C;p ++;}}// 01dpfor (int i = 1; i < p; i++) {  // 是j < p，不是是 j <= n，物品个数已经更新了，也不是<=p，因为多了一次p++for (int j = m; j >= v[i]; j--) {   // 是j >= v[i]，不是是j >= 1，数组会越界dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);}}System.out.println(dp[m]);}
}

⭕️细节：v w数组要开大一点，因为物品个数会增多，假如每个物品可以使用2000次，总共有2000个物品，就要用2000 * log2(2000) ≈ 2000 * 12

🍎笔记

多重背包，二进制优化