[Java] UVa 10130 SuperSale

題目連結

題意:
一家人逛超市
給定 N 種物品的價格與重量
還有 G 個人各自的負重上限
物品沒有購買數量上限
每個人每種物品只能買一個
求可以買到的物品最大的總價值

如:
3
6 3
8 4
10 5
2
10
12

N=3 / G=2
有 3 件物品(價/重)
2 個人，負重上限為 10, 12

第 1 個人買後兩者(總價最大)
第 2 個人買全部
總價 (8+10) + (6+8+10) = 42

解法:
典型的 0/1 背包問題 (0/1 knapsack problem)
也就是在負重上限前提下
選擇價值最高的物品組合

0/1是指物品只能要或不要
(若沒有 0/1 就是物品可以要 小於 1 份)

觀察題意可以發現
每個人的情況彼此互不影響
也就是各自進行 0/1 背包問題後加總即可

題目規定背包容量上限只有 30
所以可以預先建表(很小)
計算 1 ~ 30 各重量的最大價值
最後直接得解加總

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int T = sc.nextInt();
	while (T-- > 0) {
	int N = sc.nextInt();
	int P[] = new int[N];
	int W[] = new int[N];
	int value[] = new int[32];
	for (int i = 0; i < N; i++) {
	P[i] = sc.nextInt();
	W[i] = sc.nextInt();
	}
	for (int i = 0; i < N; i++)
	for (int j = 31; j >= 0; j--)
	if (W[i] <= j && value[j] < value[j - W[i]] + P[i])
	value[j] = value[j - W[i]] + P[i];
	int G = sc.nextInt();
	int knapsack = 0;
	for (int i = 0; i < G; i++) {
	int MW = sc.nextInt();
	knapsack += value[MW];
	}
	System.out.println(knapsack);
	}
	}
	}

view raw UVa10130.java hosted with ❤ by GitHub