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
3
votes
1
answer
1k
views
Knock down tall buildings
I'm trying to solve the following problem:
As you know Bob likes to destroy the buildings.
There are N buildings in a city, ith building has ai floors.
Bob can do the following operation.
Choose a ...
- 222
1
vote
1
answer
206
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
6
votes
1
answer
381
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 ...
- 355
1
vote
1
answer
190
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
770
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 ...
2
votes
2
answers
249
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
3
votes
1
answer
336
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
9
votes
2
answers
783
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
3
votes
0
answers
83
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
1
vote
1
answer
624
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 ...
- 151
4
votes
1
answer
121
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
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
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,619
4
votes
1
answer
745
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 a ...
- 346
4
votes
3
answers
8k
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