RULES: This is a Wiki, so please contribute by editing this post to add or modify code. Comment to state what you did, or just for the sake of commenting, but not to share code.
With this post, we start to look at slightly cooler stuff. This problem might not be as well-known as the Traveler one, but tons of people face it without realizing.
I present you the knapsack problem.
The problem involves a knapsack with limited capacity and a set of items with varying weights and values. The objective is to select a combination of items that fit within the knapsack’s capacity and maximize the total value of the selected items.
There are few variations of the problem, we will consider only two: the 0-1 and the fractional knapsack. As the names suggest, 0/1 means that an item is either in or out, the fractional means items can be divided into fractions and selected based on their contribution to the total value.
This is one of the most popular and applicable problems to solve. It pops up in construction, biology, marking, etc. So worth a try.
Feel free to try and solve one or both WITHOUT googling, wikipedia or AI.
PYTHON example for 0-1 (recursion)
def knapsack0_1(capacity, items, n):
if n == 0 or capacity == 0:
return 0
if items[n - 1][0] > capacity:
return knapsack0_1(capacity, items, n - 1)
else:
return max(
items[n - 1][1] +
knapsack0_1(capacity - items[n - 1][0], items, n - 1),
knapsack0_1(capacity, items, n - 1))
capacity = 50
items = [(10, 60), (20, 100), (30, 120), (40, 150), (25, 170), (50, 200)]
result = knapsack0_1(capacity, items, len(items))
print(result)
JavaScript example for 0-1 (non-recursive)
"use strict";
const CAPACITY = 50;
const items = [[10, 60], [20, 100], [30, 120], [40, 150], [25, 170], [50, 200]];
let result = knapsack0_1(CAPACITY, items);
console.log(result);
function knapsack0_1(capacity, items) {
let knapsack = [];
for (let item of items) {
item.push(item[1] / item[0]);
}
items.sort((a, b) => b[2] - a[2]);
while (items.length > 0) {
let [weight, value] = items.shift();
if (weight <= capacity) {
knapsack.push([weight, value]);
capacity -= weight;
}
items = items.filter(item => item[0] <= capacity);
items.sort((a, b) => b[1] - a[1]);
}
return knapsack;
}
Haskell (syntax highlight not working for some reason):
import Data.List
type Item = (Int, Int)
knapsack0_1 :: Int -> [Item] -> Int -> Int
knapsack0_1 capacity items n
| n == 0 || capacity == 0 = 0
| fst (items !! (n - 1)) > capacity = knapsack0_1 capacity items (n - 1)
| otherwise = max (snd (items !! (n - 1)) + knapsack0_1 (capacity - fst (items !! (n - 1))) items (n - 1))
(knapsack0_1 capacity items (n - 1))
main :: IO ()
main = do
let capacity = 50
let items = [(10, 60), (20, 100), (30, 120), (40, 150), (25, 170), (50, 200)]
let result = knapsack0_1 capacity items (length items)
print result
C:
#include <stdio.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int knapsack0_1(int capacity, int items[][2], int n) {
if (n == 0 || capacity == 0) {
return 0;
}
if (items[n - 1][0] > capacity) {
return knapsack0_1(capacity, items, n - 1);
} else {
return max(items[n - 1][1] + knapsack0_1(capacity - items[n - 1][0], items, n - 1),
knapsack0_1(capacity, items, n - 1));
}
}
int main() {
int capacity = 50;
int items[][2] = {{10, 60}, {20, 100}, {30, 120}, {40, 150}, {25, 170}, {50, 200}};
int itemCount = sizeof(items) / sizeof(items[0]);
int result = knapsack0_1(capacity, items, itemCount);
printf("%d\n", result);
return 0;
}
