作者aquaisaqua (aqua)
看板java
標題[問題] 良葛格網頁上的背包問題演算法
時間Sat Feb 23 11:47:20 2013
這是在良葛格網頁上
背包問題的JAVA程式碼
===============================================================================
import java.util.*;
class Fruit {
String name;
int weight;
int price;
Fruit(String name, int weight, int price) {
this.name = name;
this.weight = weight;
this.price = price;
}
public String toString() {
return String.format("(%s, %d, %d)", name, weight, price);
}
}
public class Knapsack {
public static List<Fruit> knapsack(List<Fruit> fruits, int limit) {
int[] values = new int[limit + 1];
int[] items = new int[limit + 1];
for(int i = 0; i < fruits.size(); i++) {
for(int w = fruits.get(i).weight; w <= limit; w++) {
int p = w - fruits.get(i).weight;
int newValue = values[p] + fruits.get(i).price;
if(newValue > values[w]) {
values[w] = newValue;
items[w] = i;
}
}
}
List<Fruit> solution = new ArrayList<>();
// JDK8 Lambda
int min = Collections.min(fruits
, (f1, f2) -> f1.weight - f2.weight).weight;
for(int i = limit; i >= min; i -= fruits.get(items[i]).weight) {
solution.add(fruits.get(items[i]));
}
return solution;
}
public static void main(String[] args) {
System.out.println(knapsack(Arrays.asList(
new Fruit("李子", 4, 4500), new Fruit("蘋果", 5, 5700),
new Fruit("橘子", 2, 2250), new Fruit("草莓", 1, 1100),
new Fruit("甜瓜", 6, 6700)), 8));
}
}
===============================================================================
問題1.
在 knapsack 方法中這段程式碼
for(int i = 0; i < fruits.size(); i++) {
for(int w = fruits.get(i).weight; w <= limit; w++) {
int p = w - fruits.get(i).weight;
int newValue = values[p] + fruits.get(i).price;
if(newValue > values[w]) {
values[w] = newValue;
items[w] = i;
}
}
}
的第2個for迴圈中 int p 每跑一次迴圈就會重新宣告為 int ???
int newValue
可以把 p newValue 宣告在兩個for迴圈之間也是同樣功用 ??
問題2.
在 main 方法的上方
List<Fruit> solution = new ArrayList<>();
---------
會出現以下錯誤訊息
==== '<>' operator is not allowed for source level below 1.7 =====
我該怎麼調整版本讓他可以編譯過 ???
問題3.
在 main 方法的上方
int min = Collections.min(fruits
, (f1, f2) -> f1.weight - f2.weight).weight;
這一段程式碼中的 f1 f2 是不是忘記宣告??
謝謝版上大大!!!!!
感恩~~~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.171.181.150
※ 編輯: aquaisaqua 來自: 118.171.181.150 (02/23 11:57)
1F：推 PsMonkey:1. 自己試試看就知道了 2. 註解有說要 JDK8 ==.=== 02/23 12:25
2F：→ coolcomm:2.是SE7的新語法 constuctor的泛型型態可以省略 02/23 12:31
3F：→ coolcomm:3.是SE8的Lambda ... 註解裡有寫 02/23 12:33
4F：→ aquaisaqua:感謝!!!!! 02/23 12:40
5F：→ SansWord:2 的話就改成 ArrayList<Fruit> 就可以在 SE7 編過了 02/25 10:47