KnapsackProblem

Posted on

KnapsackProblem

[Algorithm Gossip: 背包问题(Knapsack Problem)]

说明

假设有一个背包的负重最多可达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]); } }
希望本站内容对您有点用处,有什么疑问或建议请在后面留言评论
转载请注明作者(RobinChia)和出处 It so life ,请勿用于任何商业用途
本文链接: KnapsackProblem