This content originally appeared on DEV Community and was authored by 0xc0Der
The knapsack problem is a classic problem in combinatorial optimization:
The knapsack problem has been studied for more than a century, with early works dating as far back as 1897.
And the problem statement is:
Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Sounds simple right? We just need to maximize the value of the items in the sack while keeping the weight under a certain threshold.
Turns out that it's not that easy. the problem is NP-complete, and that means that there is no known algorithm to solve it in polynomial time.
There are already algorithms out there to solve the problem, But they get exponentially slow for large inputs. Which is not very good at all.
First, the knapsack problem is in its simplest form is called 0-1 knapsack problem which is I am going to focus on.
I tried to solve it by assigning a cost to each element, But what could it be?
here I'll just go with cost = weight / value. simple but good estimate.
then add the elements to the sack form the lest cost till it hits the max capacity.
Lets look at the implementation. I've written it in JavaScript. good language for fast prototyping.
// item[0] is item's weight
// item[1] is item's value
const cost = item => item[0] / item[1];
const sorted = items => items.sort((a, b) => {
const [ca, cb] = [cost(a), cost(b)];
return ca == cb ? a.weight > b.weight : ca > cb;
});
const solve = (items, capacity) => {
const sack = {
items: [],
capacity,
weight: 0,
value: 0
};
for (const item of sorted(items)) {
if (sack.weight + item[0] <= capacity) {
sack.items.push(item);
sack.weight += item[0];
sack.value += item[1];
}
}
return sack;
};
And that's it. Please let me know what you think.
Thanks for reading 😄.
This content originally appeared on DEV Community and was authored by 0xc0Der
0xc0Der | Sciencx (2024-08-24T12:14:54+00:00) attacking the knapsack problem.. Retrieved from https://www.scien.cx/2024/08/24/attacking-the-knapsack-problem/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.