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.

Filter by
Sorted by
Tagged with
19
votes
3answers
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....
3
votes
1answer
155 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 ...
3
votes
1answer
92 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 ...
0
votes
0answers
92 views

Swift Knapsack problem using bottom-down (memoization) approach

I'm solving the "unbounded" variant of the knapsack problem, meaning the repetition of items is allowed. As in the Hackerrank version of the knapsack problem, I am returning the sum nearest to, not ...
3
votes
2answers
1k 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 ...
1
vote
2answers
75 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 ...
4
votes
1answer
92 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. ...
3
votes
0answers
99 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 ...
3
votes
2answers
140 views

Knapsack01 problem, written in c#

Is this code written in a decent style? Appreciate some feedback : ) ...
2
votes
0answers
35 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 ...
1
vote
1answer
511 views

Fractional knapsack implementation in Python

...
4
votes
0answers
791 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 ...
4
votes
1answer
740 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 ...
3
votes
0answers
259 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. <...
3
votes
0answers
551 views

Find smallest subset of integers having a given sum

Write a function that meets the specifications below: ...
6
votes
2answers
6k 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? ...
4
votes
3answers
1k views

Python Knapsack greedy

Given a dictionary of cows and their weight: ...
2
votes
1answer
142 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 ...
3
votes
2answers
3k views

Subset sum problem implementation

Here is a recursive implementation of the Subset sum problem: ...
3
votes
1answer
201 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 ...
3
votes
3answers
270 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
votes
2answers
985 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 ...
5
votes
1answer
392 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 ...
2
votes
0answers
279 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. ...
6
votes
2answers
2k 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 ...
2
votes
1answer
555 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 ...
5
votes
0answers
644 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 ...
6
votes
1answer
1k 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 ...
1
vote
1answer
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. ...
4
votes
1answer
2k 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, ...
46
votes
2answers
61k 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 ...