說明
假設有一個背包的負重最多可達8公斤,而希望在背包中裝入負重範圍內可得之總價物品,假設是水果好了,水果的編號、單價與重量如下所示:
0 |
李子 |
4KG |
NT$4500 |
1 |
蘋果 |
5KG |
NT$5700 |
2 |
橘子 |
2KG |
NT$2250 |
3 |
草莓 |
1KG |
NT$1100 |
4 |
甜瓜 |
6KG |
NT$6700 |
解法
背包問題是關於最佳化的問題,要解最佳化問題可以使用「動態規劃」(Dynamic
programming),從空集合開始,每增加一個元素就先求出該階段的最佳解,直到所有的元素加入至集合中,最後得到的就是最佳解。
以背包問題為例,我們使用兩個陣列value與item,value表示目前的最佳解所得之總價,item表示最後一個放至背包的水果,假設有負重量
1~8的背包8個,並對每個背包求其最佳解。
逐步將水果放入背包中,並求該階段的最佳解:
背包負重 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
value |
0 |
0 |
0 |
4500 |
4500 |
4500 |
4500 |
9000 |
item |
- |
- |
- |
0 |
0 |
0 |
0 |
0 |
背包負重 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
value |
0 |
0 |
0 |
4500 |
5700 |
5700 |
5700 |
9000 |
item |
- |
- |
- |
0 |
1 |
1 |
1 |
0 |
背包負重 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
value |
0 |
2250 |
2250 |
4500 |
5700 |
6750 |
7950 |
9000 |
item |
- |
2 |
2 |
0 |
1 |
2 |
2 |
0 |
背包負重 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
value |
1100 |
2250 |
3350 |
4500 |
5700 |
6800 |
7950 |
9050 |
item |
3 |
2 |
3 |
0 |
1 |
3 |
2 |
3 |
背包負重 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
value |
1100 |
2250 |
3350 |
4500 |
5700 |
6800 |
7950 |
9050 |
item |
3 |
2 |
3 |
0 |
1 |
3 |
2 |
3 |
由最後一個表格,可以得知在背包負重8公斤時,最多可以裝入9050元的水果,而最後一個裝入的
水果是3號,也就是草莓,裝入了草莓,背包只能再放入7公斤(8-1)的水果,所以必須看背包負重7公斤時的最佳解,最後一個放入的是2號,也就
是橘子,現在背包剩下負重量5公斤(7-2),所以看負重5公斤的最佳解,最後放入的是1號,也就是蘋果,此時背包負重量剩下0公斤(5-5),無法
再放入水果,所以求出最佳解為放入草莓、橘子與蘋果,而總價為9050元。
JAVA代码解答:
class Fruit { private String name; private int size; private int price; public Fruit(String name, int size, int price) { this.name = name; this.size = size; this.price = price; } public String getName() { return name; }
public int getPrice() { return price; }
public int getSize() { return size; } }
public class Knapsack { public static void main(String[] args) { final int MAX = 8; final int MIN = 1; int[] item = new int[MAX+1]; int[] value = new int[MAX+1];
Fruit fruits[] = { new Fruit("李子", 4, 4500), new Fruit("蘋果", 5, 5700), new Fruit("橘子", 2, 2250), new Fruit("草莓", 1, 1100), new Fruit("甜瓜", 6, 6700)};
for(int i = 0; i < fruits.length; i++) { for(int s = fruits[i].getSize(); s <= MAX; s++) { int p = s - fruits[i].getSize(); int newvalue = value[p] + fruits[i].getPrice(); if(newvalue > value[s]) {// 找到階段最佳解 value[s] = newvalue; item[s] = i; } } }
System.out.println("物品\t價格"); for(int i = MAX; i >= MIN; i = i - fruits[item[i]].getSize()) { System.out.println(fruits[item[i]].getName()+ "\t" + fruits[item[i]].getPrice()); }
System.out.println("合計\t" + value[MAX]); } }
|