2015/2 - PAA: Knapsack Usando Estratégia Gulosa (Groovy)

import static java.math.RoundingMode.*

def knapsackCont = { list, maxWeight = 15.0 ->
    for (item in list) {
        item.benefit = item.value/item.weight
        item.benefit = (item.benefit as BigDecimal).setScale(2, HALF_UP)
    }
    println 'before sort: ' + list
    list.sort{ it.weight / it.value }
    println 'after sort: ' + list
    def remainder = maxWeight
    println 'max weight: ' + maxWeight
    List sack = []
    for (item in list) {
        if (item.weight < remainder) {
            sack << [item]
        } else {
            sack << [item]
            break
        }
        remainder -= item.weight
        println 'remainder: ' + remainder
    }
    sack
}

def possibleItems = [
    [name:'green',    weight:12, value:4, benefit: 0],
    [name:'gray',    weight:1, value:2, benefit: 0],
    [name:'yellow',     weight:4, value:10, benefit: 0],
    [name:'blue', weight:2, value:2, benefit: 0],
    [name:'orange',  weight:1, value:1, benefit: 0],
]

def contents = knapsackCont(possibleItems)
println "Total Value: ${contents*.value.sum()}"
contents.each {
    printf("    name: %-7s  weight: ${it.weight}  value: ${it.value}  benefit: ${it.benefit}\n", it.name)
}