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.
41
questions
57
votes
3
answers
69k
views
Dynamic programming knapsack solution
I wrote a solution to the Knapsack problem in Python, using a bottom-up dynamic programming algorithm. It correctly computes the optimal value, given a list of items with values and weights, and a ...
- 852
21
votes
3
answers
4k
views
Loading military units into ships optimally, using backtracking
I solved the following problem using backtracking:
We are given a list of military units, their weight and their
(numerical) strength. We have a number of ships with a limited
carrying capacity....
- 313
9
votes
2
answers
718
views
0/1 knapsack algorithm implementation with possibilities vector
The following code uses dynamic approach to solve 0/1 knapsack problem. (I know the maximum profit function I have used is not as good as the one I have defined ...
- 354
8
votes
2
answers
4k
views
Knapsack algorithm in JavaScript - Integer weights and values
My version of Knapsack works only when the weights or values of items are whole numbers.
Restrictions
You are given an array of objects each of which contains a weight and value.
You are also given ...
- 81
6
votes
2
answers
8k
views
Knapsack greedy algorithm in Python
I implemented the well-known knapsack problem and now I would like to improve it using list comprehension or lambda. I don't want to use NumPy. Could you help me?
...
- 285
6
votes
1
answer
2k
views
Python Knapsack problem: greedy
A tourist wants to make a good trip at the weekend with his friends. They will go to the mountains to see the wonders of nature, so he needs to pack well for the trip. He has a good knapsack for ...
- 27.4k
6
votes
3
answers
2k
views
6
votes
1
answer
727
views
Multiple 0-1 knapsack
I have a problem were the time in minutes of N songs are given and I have to write the maximum number of time in K CDs.
Input description
The first input line consists of two positive integers N e K (...
- 597
5
votes
2
answers
2k
views
Change-making problem with specific constraints
I am a new Pythoner. I have solved a OJ project with Python. Can you tell me how can I solve it more Pythonically?
Problem Description: There are n coin denominations, each with an unlimited supply ...
- 145
5
votes
1
answer
676
views
Stampcalculator - Given a set of stamps, what combinations are there to reach a certain amount?
Background
My mother has a hobby of buying and reselling books via online trading sites. After a price is agreed on, the books have to be put into an envelope for mailing. On this envelope, stamps ...
- 22.3k
4
votes
3
answers
7k
views
Knapsack problem - recursive approach with memoization
This post is based on the 0-1 Knapsack problem. I came across this problem in Assignment #4 of Professor Tim Roughgarden's course Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming on ...
user188780
4
votes
1
answer
110
views
Find subset with largest talent to weight ratio, subject to minimum weight
I'm using some old USA Computing Olympiad (USACO) problems to help teach me programming. This is the second one I've posted, I hope that's okay -- let me know if this is considered abusing the system. ...
- 151
4
votes
1
answer
178
views
Bin-packing C++ solution using multi-map
The need (context).
Several times a day, we need to migrate a set of digital assets from one system to another. The process uses memory (the assets are held in memory for a short time) and we need to ...
- 197
4
votes
1
answer
94
views
Solving the knapsack problem with user provided input
This question was given in my college assignment to be done in C. After doing that, I rewrote the program again in rust.
I come from a C/Python background and this is my first rust program. Please ...
- 141
4
votes
1
answer
3k
views
Recursive branch and bound Knapsack solution [closed]
I've got the imperative styled solution working perfectly.
What I'm wondering is how to make a recursive branch and bound.
This is my code below. Evaluate function returns the optimistic estimate, ...
- 143
4
votes
1
answer
680
views
Find out how many laptops Molly can buy based on available money, array of quantities and array of costs
Problem description:
Molly wants to purchase laptops for her school. Find out how many laptops she can purchase by comparing the vendors available.
Each vendor sells the laptops in batches, with ...
- 306
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
2
answers
4k
views
Subset sum problem implementation
Here is a recursive implementation of the Subset sum problem:
...
- 1,174
3
votes
3
answers
336
views
Fractional Knapack as asked in an interview
Description:
Given the Knapsack capacity and the weight and value of some items,
find a way to maximize the value in the given Knapsack.
Code:
...
- 5,087
3
votes
1
answer
2k
views
Python program for "0-1 knapsack problem"
Here is what a knapsack/rucksack problem means (taken from Wikipedia):
Given a set of items, each with a weight and a value, determine the
number of each item to include in a collection so that ...
- 2,468
3
votes
2
answers
162
views
Knapsack01 problem, written in c#
Is this code written in a decent style? Appreciate some feedback : )
...
- 31
3
votes
1
answer
271
views
Is this an optimal implementation for the knapsack algorithm?
I have implemented a solution for the knapsack problem while breaking an item is allowed. I've used the dictionary data structure where I used weight as a key and value per weight as a value. After ...
- 141
3
votes
1
answer
447
views
Code for dividing gifts equally
I recently came across this problem:
It is Lavanya's birthday and several families have been invited for
the birthday party. As is customary, all of them have brought gifts
for Lavanya as well ...
- 389
3
votes
1
answer
1k
views
Knapsack problem with duplicate elements
I solved the knapsack problem where duplicates elements are allowed:
Given weights and values related to n items and the maximum capacity allowed for these items. What is the maximum value we can ...
- 1,281
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
2
answers
175
views
Knapsack performance issue
I'm solving a knapsack problem here. It works, but gives time limit exceeds on a certain test case.
Problem statement
There are N
items, numbered 1,2,…,N. For each i (1≤i≤N), Item i has a weight of ...
- 167
2
votes
1
answer
640
views
Fractional Knapsack
This is my solution to an assignment on the fractional Knapsack problem. I take as problem input the following pieces of information:
The number of item types
The total weight limit
For each item ...
- 21
2
votes
1
answer
164
views
0-1 Knapsack problem - implementation
Given a set of items with a weight and a value, this problem gives the subset of items which maximize value so that their combined weights is less or equal than a given maximum weight. This solution ...
- 2,954
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
2
answers
154
views
Knapsack class in Ruby
This is a simple implementation of a knapsack written in Ruby. I've included all the relevant code here, but my question is concerning the contents setter ...
- 179
1
vote
1
answer
114
views
A greedy approach to the Knapsack problem with C++ templates
The assignment is to be implemented on the following instructions:
You are to write a Knapsack class and the main() to support and
demonstrate the functionality required here.
A function generate(int)...
user266090
1
vote
1
answer
696
views
1
vote
1
answer
1k
views
Knapsack 01 solution
Solution to bounded knapsack 01 problem. Once again comprehensive description is difficult in this space, refer here. Looking for code review. optimizations and best practices.
...
- 8,391
1
vote
1
answer
119
views
Continuous knapsack problem in Rust
Background
The continuous knapsack problem is the following linear program:
$$
\begin{align}
\text{maximize} \quad & f(x) = \sum_{i=1}^n u_i x_i \\
\text{subject to} \quad & \...
- 207
1
vote
0
answers
578
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
1
answer
546
views
Solution to knapsack problem exceeds time and RAM limits
My goal is to code the knapsack problem algorithm. The problem is that a knapsack has a given weight limit, W. I have a collection of items which have a given ...
- 141
0
votes
0
answers
33
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 ...
