當(dāng)前位置:首頁(yè) > IT技術(shù) > 其他 > 正文

多重背包問(wèn)題——二進(jìn)制優(yōu)化
2022-04-29 13:54:20

前言

二進(jìn)制優(yōu)化,將每類(lèi)物品的數(shù)量按2的整數(shù)次冪進(jìn)行拆分,因?yàn)槿魏我粋€(gè)十進(jìn)制數(shù)都可以用若干個(gè)二進(jìn)制數(shù)來(lái)湊成

時(shí)間復(fù)雜度:O(NlogSV)

題目描述

有 N 種物品和一個(gè)容量是 V 的背包。

第 i 種物品最多有 si 件,每件體積是 vi,價(jià)值是 wi。

求解將哪些物品裝入背包,可使物品體積總和不超過(guò)背包容量,且價(jià)值總和最大。
輸出最大價(jià)值。

輸入格式

第一行兩個(gè)整數(shù),N,V,用空格隔開(kāi),分別表示物品種數(shù)和背包容積。

接下來(lái)有 N 行,每行三個(gè)整數(shù) vi,wi,si,用空格隔開(kāi),分別表示第 i 種物品的體積、價(jià)值和數(shù)量。

輸出格式

輸出一個(gè)整數(shù),表示最大價(jià)值。

數(shù)據(jù)范圍

0<N1000
0<V2000
0<vi,wi,si2000

提示:

本題考查多重背包的二進(jìn)制優(yōu)化方法。

輸入樣例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

輸出樣例:

10

Java代碼

 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         // 拆分后的物品種類(lèi)
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/

開(kāi)通會(huì)員,享受整站包年服務(wù)立即開(kāi)通 >