The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively. Knapsack 0/1 problem doesn’t allow fractional weights.

fun knapsack01(input: List<Pair<Int, Int>>, limit: Int): IntArray {
    val result = IntArray(input.size) { 0 }
    val n = input.size
    val dp = Array(n + 1) { IntArray(limit + 1) { 0 } }
    input.sortedBy { it.first }
    for (i in 1..n) {
        for (j in 1..limit) {
            val (weight, cost) = input[i - 1]
            dp[i][j] = when {
                j - weight >= 0 -> {
                    maxOf(dp[i - 1][j], dp[i-1][j - weight] + cost)
                }
                else -> dp[i - 1][j]
            }
        }
    }

    var column = limit
    for (i in n - 1 downTo 0) {
        result[i] = when {
            i == 0 && column != 0 -> 1
            i == 0 && column == 0 -> 0
            dp[i][column] == dp[i - 1][column] -> 0
            else -> {
                column -= input[i].first
                1
            }
        }
    }
    return result
}

Knapsack fractional weight uses greedy algorithm

fun knapsackFraction(weights: IntArray, cost: IntArray, limit: Int): Double {
    var total = 0.0
    val input = weights.mapIndexed { index, i -> Pair(i, cost[index]) }
    input.sortedByDescending { it.second.toDouble() / it.first }
    var remaining = limit
    for (i in input.indices) {
        if (remaining < input[i].first) {
            total += (remaining * input[i].second.toDouble() / input[i].first)
            break
        } else {
            remaining -= input[i].first
            total += input[i].second.toDouble()
        }
    }
    return total
}