# Language vs algorithm part 3: The knapsack problem

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] > capacity:
return knapsack0_1(capacity, items, n - 1)
else:
return max(
items[n - 1] +
knapsack0_1(capacity - items[n - 1], 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 / item);
}

items.sort((a, b) => b - a);

while (items.length > 0) {
let [weight, value] = items.shift();
if (weight <= capacity) {
knapsack.push([weight, value]);
capacity -= weight;
}
items = items.filter(item => item <= capacity);
items.sort((a, b) => b - a);
}
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[], int n) {
if (n == 0 || capacity == 0) {
return 0;
}
if (items[n - 1] > capacity) {
return knapsack0_1(capacity, items, n - 1);
} else {
return max(items[n - 1] + knapsack0_1(capacity - items[n - 1], items, n - 1),
knapsack0_1(capacity, items, n - 1));
}
}

int main() {
int capacity = 50;
int items[] = {{10, 60}, {20, 100}, {30, 120}, {40, 150}, {25, 170}, {50, 200}};
int itemCount = sizeof(items) / sizeof(items);

int result = knapsack0_1(capacity, items, itemCount);
printf("%d\n", result);

return 0;
}
``````
4 Likes

Just a note, this is not currently a wiki. Figured I should point that out.

2 Likes

isn’t*

Fixed. I forgot to do it, sorry.

haha, I don’t think we know the dynamic programming XD. Is recursion allowed?

edit: don’t really know the dp off the top of my head ;-;

1 Like

You love algorithms right?

yes but I haven’t practiced in a hot second so I don’t think I could code it from scratch

1 Like

I suck at recursion Anything is allowed except using AI or copying code. Give it a try as this is something very common. Worst case peep into my python public repl (PlayingWithPython)

1 Like

Then this will help 1 Like

bruh I know it’s very common ;-; man taking a break from this stuff really make people think I can’t do it

1 Like

He was talking to me ;-;

I thought he was talking to me…

well anyway, it’s ok I’ll stop

2 Likes

I just clicked the wrong thing … sorry bmb. I guess I will need to post an example soon 3 Likes

is ok sorry I overreacted

1 Like

The 1 to 0 knapsack problem is an intriguing. If you try to make efficient algorithm that can swiftly compute the optimal value-to-weight ratio for a given set of items, and then determine the most likely combination of items that yield the highest value. However, achieving 100% certainty that the solution is absolutely the best in all scenarios is exceedingly difficult with fast algorithms that try to avoid brute force all combinations to be 100% sure.

While a brute-force algorithm that evaluates all possible combinations guarantee the optimal solution in all cases but it is very slow.

2 Likes

Give it a try and calculate the error, you might be surprised that often the error is acceptable I have added a non-recursive JavaScript version of 0 to 1 knapsack. Here’s how it works: first, it calculates the weight-to-value ratio for each item. It then sorts all items by this ratio, with the items that provide the best ratio appearing at the top of the array. The algorithm then proceeds to insert items into the knapsack, starting from the top of the array and working its way down. It prioritizes items with the best weight-to-value ratio, and ignores any items that can’t fit into the knapsack.

This algorithm probably give good results most of cases but I’m fairly sure it wont give optimum result in every case.

1 Like

Great. Why not try to make also the comprehensive solution and run a little comparison?

I need to improve my algorithm I bit I just realized it gives second best solution not best.

My algorithm calculate that items [25, 170] and [10, 60] give best results but you can get better with [25, 170] and [20, 100].

My algorithm total value is 230 but you can go 270 total with those other items. EDIT: I have made an update to my algorithm. After it inserts the item with the best weight-to-value ratio into the knapsack, it filters out any items that can no longer fit into the remaining space. It then prioritizes items that fit into the remaining space and provide the best value instead of inserting item that have best weight to value ratio witch could leave large empty space in knapsack if best to weight ratio item is small but causes other items not to fit anymore. But I think this solution also have its limitations and wont give optimum result every case but at least in this case it gives it better than previous version. So now it give [25, 170] and [20, 100] as result.

2 Likes