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
Filter by
Sorted by
Tagged with
4 votes
0 answers

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 ...
epsilon8's user avatar
  • 141
3 votes
0 answers

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 ...
Holli's user avatar
  • 221
3 votes
0 answers

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 ...
vbvvv20's user avatar
  • 41
3 votes
0 answers

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. <...
rnso's user avatar
  • 241
3 votes
0 answers

Find smallest subset of integers having a given sum

Write a function that meets the specifications below: ...
Tao Xu's user avatar
  • 91
2 votes
0 answers

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 ...
ng.newbie's user avatar
  • 171
2 votes
0 answers

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. ...
mgabz's user avatar
  • 121
1 vote
0 answers

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 ...
Jose Fernando Lopez Fernandez's user avatar
0 votes
0 answers

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 ...
Some nerd who does not have a 's user avatar