99 lines
3.3 KiB
Scala
99 lines
3.3 KiB
Scala
object Knapsack extends App {
|
|
|
|
case class Item(name: String, weight: Int, value: Int)
|
|
|
|
val elapsed: (=> Unit) => Long = f => {val s = System.currentTimeMillis; f; (System.currentTimeMillis - s)/1000}
|
|
|
|
//===== brute force (caution: increase the heap!) ====================================
|
|
val ks01b: List[Item] => Unit = loi => {
|
|
val tw:Set[Item]=>Int=ps=>(ps:\0)((a,b)=>a.weight+b) //total weight
|
|
val tv:Set[Item]=>Int=ps=>(ps:\0)((a,b)=>a.value+b) //total value
|
|
val pis = (loi.toSet.subsets).toList.filterNot(_==Set())
|
|
|
|
#[test]
|
|
fn test_dp_results() {
|
|
let dp_results = knap_01_dp(items, 400);
|
|
let dp_weights= dp_results.iter().fold(0, |a, &b| a + b.weight);
|
|
let dp_values = dp_results.iter().fold(0, |a, &b| a + b.value);
|
|
assert_eq!(dp_weights, 396);
|
|
assert_eq!(dp_values, 1030);
|
|
} val res = pis.map(ss=>Pair(ss,tw(ss)))
|
|
.filter(p=>p._2>350 && p._2<401).map(p=>Pair(p,tv(p._1)))
|
|
.sortWith((s,t)=>s._2.compareTo(t._2) < 0)
|
|
.last
|
|
println{val h = "packing list of items (brute force):"; h+"\n"+"="*h.size}
|
|
res._1._1.foreach{p=>print(" "+p.name+": weight="+p.weight+" value="+p.value+"\n")}
|
|
println("\n"+" resulting items: "+res._1._1.size+" of "+loi.size)
|
|
println(" total weight: "+res._1._2+", total value: "+res._2)
|
|
}
|
|
|
|
//===== dynamic programming ==========================================================
|
|
val ks01d: List[Item] => Unit = loi => {
|
|
val W = 400
|
|
val N = loi.size
|
|
|
|
val m = Array.ofDim[Int](N+1,W+1)
|
|
val plm = (List((for {w <- 0 to W} yield Set[Item]()).toArray)++(
|
|
for {
|
|
n <- 0 to N-1
|
|
colN = (for {w <- 0 to W} yield Set[Item](loi(n))).toArray
|
|
} yield colN)).toArray
|
|
|
|
1 to N foreach {n =>
|
|
0 to W foreach {w =>
|
|
def in = loi(n-1)
|
|
def wn = loi(n-1).weight
|
|
def vn = loi(n-1).value
|
|
if (w<wn) {
|
|
m(n)(w) = m(n-1)(w)
|
|
plm(n)(w) = plm(n-1)(w)
|
|
}
|
|
else {
|
|
if (m(n-1)(w)>=m(n-1)(w-wn)+vn) {
|
|
m(n)(w) = m(n-1)(w)
|
|
plm(n)(w) = plm(n-1)(w)
|
|
}
|
|
else {
|
|
m(n)(w) = m(n-1)(w-wn)+vn
|
|
plm(n)(w) = plm(n-1)(w-wn)+in
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
println{val h = "packing list of items (dynamic programming):"; h+"\n"+"="*h.size}
|
|
plm(N)(W).foreach{p=>print(" "+p.name+": weight="+p.weight+" value="+p.value+"\n")}
|
|
println("\n"+" resulting items: "+plm(N)(W).size+" of "+loi.size)
|
|
println(" total weight: "+(0/:plm(N)(W).toVector.map{item=>item.weight})(_+_)+", total value: "+m(N)(W))
|
|
}
|
|
|
|
val items = List(
|
|
Item("map", 9, 150)
|
|
,Item("compass", 13, 35)
|
|
,Item("water", 153, 200)
|
|
,Item("sandwich", 50, 160)
|
|
,Item("glucose", 15, 60)
|
|
,Item("tin", 68, 45)
|
|
,Item("banana", 27, 60)
|
|
,Item("apple", 39, 40)
|
|
,Item("cheese", 23, 30)
|
|
,Item("beer", 52, 10)
|
|
,Item("suntan cream", 11, 70)
|
|
,Item("camera", 32, 30)
|
|
,Item("t-shirt", 24, 15)
|
|
,Item("trousers", 48, 10)
|
|
,Item("umbrella", 73, 40)
|
|
,Item("waterproof trousers", 42, 70)
|
|
,Item("waterproof overclothes", 43, 75)
|
|
,Item("note-case", 22, 80)
|
|
,Item("sunglasses", 7, 20)
|
|
,Item("towel", 18, 12)
|
|
,Item("socks", 4, 50)
|
|
,Item("book", 30, 10)
|
|
)
|
|
|
|
List(ks01b, ks01d).foreach{f=>
|
|
val t = elapsed{f(items)}
|
|
println(" elapsed time: "+t+" sec"+"\n")
|
|
}
|
|
}
|