作者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