# 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
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
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
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
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
781 views

### Find smallest subset of integers having a given sum

Write a function that meets the specifications below: ...
• 91
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
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