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()
}
}