APP
前言
二進(jìn)制優(yōu)化，將每類物品的數(shù)量按2的整數(shù)次冪進(jìn)行拆分，因?yàn)槿魏我粋€(gè)十進(jìn)制數(shù)都可以用若干個(gè)二進(jìn)制數(shù)來湊成
時(shí)間復(fù)雜度：O(NlogSV)
題目描述
有 N 種物品和一個(gè)容量是 V 的背包。
第 i 種物品最多有 si 件，每件體積是 vi，價(jià)值是 wi。
求解將哪些物品裝入背包，可使物品體積總和不超過背包容量，且價(jià)值總和最大。
輸出最大價(jià)值。
輸入格式
第一行兩個(gè)整數(shù)，N，V，用空格隔開，分別表示物品種數(shù)和背包容積。
接下來有 N 行，每行三個(gè)整數(shù) vi,wi,si，用空格隔開，分別表示第 i 種物品的體積、價(jià)值和數(shù)量。
輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。
數(shù)據(jù)范圍
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
提示：
本題考查多重背包的二進(jìn)制優(yōu)化方法。
輸入樣例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
輸出樣例：
10Java代碼
1 import java.util.*; 2 3 public class Main { 4 5 static int N = 25000 + 10; 6 static int[] f = new int[N]; 7 static int[] v = new int[N]; 8 static int[] w = new int[N]; 9 10 public static void main(String[] args) { 11 Scanner in = new Scanner(System.in); 12 int n = in.nextInt(); 13 int m = in.nextInt(); 14 15 // 拆分后的物品種類 16 int cnt = 0; 17 while (n-- > 0) { 18 int a = in.nextInt(); 19 int b = in.nextInt(); 20 int s = in.nextInt(); 21 int k = 1; 22 while (k <= s) { 23 cnt++; 24 v[cnt] = a * k; 25 w[cnt] = b * k; 26 s -= k; 27 k *= 2; 28 } 29 if (s > 0) { 30 cnt++; 31 v[cnt] = a * s; 32 w[cnt] = b * s; 33 s -= s; 34 } 35 } 36 37 // 更新n 38 n = cnt; 39 40 // 01背包 41 for (int i = 1; i <= n; i++) { 42 for (int j = m; j >= v[i]; j--) { 43 f[j] = Math.max(f[j], f[j - v[i]] + w[i]); 44 } 45 } 46 47 System.out.println(f[m]); 48 } 49 50 }
?
本文摘自 ：https://www.cnblogs.com/
