Relaxed Achievable Maximum

relaxed_achievable_maximum.kt

fun main(args: Array<String>) {

    class Item(val weight: Double, val value: Double)

    val items = listOf(
            Item(1.0, 2.0),
            Item(2.0, 4.0),
            Item(3.0, 6.0)
    )

    items.relaxedAchievableMaximum(4.0, {it.weight},{it.value}).run(::println)
}

/**
 * Maximize value of grabbed items given their weights
 */
inline fun <T> List<T>.relaxedAchievableMaximum(knapsackCapacity: Double,
                                                crossinline weightMapper: (T) -> Double,
                                                crossinline valueMapper: (T) -> Double
) = sortedByDescending { valueMapper(it) / weightMapper(it) }
                .let { sorted ->
                    var achievableWeight = 0.0
                    var achievableValue = 0.0
                    var i = 0
                    val itemCount = sorted.size

                    while (i < itemCount && (achievableWeight + weightMapper(sorted[i])) <= knapsackCapacity) {
                        achievableWeight += weightMapper(sorted[i])
                        achievableValue += valueMapper(sorted[i])
                        i++
                    }

                    if (i < itemCount) {
                        val remainderItem = sorted[i]

                        val remainderRatio = (knapsackCapacity - achievableWeight) / weightMapper(remainderItem)
                        achievableValue += (remainderRatio * valueMapper(remainderItem))
                    }

                    achievableValue
                }



inline fun <T> List<T>.relaxedAchievableMinimum(knapsackCapacity: Double,
                                      crossinline weightMapper: (T) -> Double,
                                      crossinline valueMapper: (T) -> Double
) = sortedBy { valueMapper(it) / weightMapper(it) }
        .let { sorted ->
            var achievableWeight = 0.0
            var achievableValue = 0.0
            var i = 0
            val itemCount = sorted.size

            while (i < itemCount && (achievableWeight + weightMapper(sorted[i])) <= knapsackCapacity) {
                achievableWeight += weightMapper(sorted[i])
                achievableValue += valueMapper(sorted[i])
                i++
            }

            if (i < itemCount) {
                val remainderItem = sorted[i]

                val remainderRatio = (knapsackCapacity - achievableWeight) / weightMapper(remainderItem)
                achievableValue += (remainderRatio * valueMapper(remainderItem))
            }

            achievableValue
        }