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

🍎筆記

多重背包，二進制優化