Questions tagged [knapsack-problem]
The knapsack problem is a problem in combinatorial optimization: Given a set of items with associated weights and values, 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 it maximizes the total value. It is an NP-complete problem, but several common simplifications are solved efficiently with dynamic programming.
9
questions with no upvoted or accepted answers
4
votes
0
answers
311
views
Knapsack 0-1 in Rust
Here is an implementation of Knapsack in Rust. How could it be improved?
Some things I have already spotted:
What would be the best way to extract result? Is using an option preferred unwrapping the ...
- 141
3
votes
0
answers
71
views
Raku and the Knapsack
The following is a solution to the knapsack problem and supposed to be my entry to this weeks perl challenge. I wonder if this is a good use of dynamic variables or is it too confusing?
I use them ...
- 221
3
votes
0
answers
958
views
Finding combination of coins that can produce a given sum
This function is checking, whether it has enough money in a list called self.deviceMoney to make change.
It works exactly the way I want, but only in case where ...
- 41
3
votes
0
answers
665
views
Knapsack solution in Scheme/Racket
Following is my solution to Knapsack problem using all combinations of the sent list of items (in Racket programming language). Although it is very short, I am sure it can be improved in many ways.
<...
- 241
3
votes
0
answers
781
views
Find smallest subset of integers having a given sum
Write a function that meets the specifications below:
...
- 91
2
votes
0
answers
47
views
Optimizations for Knapsack with 3 dimensions
Problem Statement:
I am given a set of prices for \$n\$ items I have to find out what is the maximum value I can get with \$M\$ money by selecting exactly \$C\$ items without exceeding the amount of ...
- 171
2
votes
0
answers
399
views
Unbounded knapsack solution with items of equal value
My solution correctly solves the problem, but I would like to optimize its performance. For a capacity of 7 and bars = [ 4, 1, 1, 2, 1], the output is 7.
...
- 121
1
vote
0
answers
579
views
Solving the Knapsack Problem With a Genetic Algorithm Simulation in Python
I was watching Computerphile's video on using genetic algorithms to solve the Knapsack problem, and I decided to give it a whack.
For anyone running the code, the ...
0
votes
0
answers
34
views
Make efficiency of book buying algorithm better
Suppose you have n books. Let the prices of the books be x0, x1, x2, ... , x(n-1) and let the corresponding amounts of pages in each book be y0, y1, ..., y(n-1). You have Z amount of money and you ...
