Stack Overflow
Stack Overflow

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.

There are several variants of the knapsack problem, such as 0-1 knapsack problem, bounded and unbounded knapsack problem. The unbounded and 0-1 knapsack are solved efficiently by using divide-and-conquer techniques (dynamic programming).

Other variants, where one can take a non-integer amount of an item, the weights are real numbers (and instances where other constraints become real instead of integer) are NP-complete.

A multiple knapsack problem is often referred to as the bin-packing problem.

1098 questions
116
votes
5 answers

Why is the knapsack problem pseudo-polynomial?

I know that Knapsack is NP-complete while it can be solved by DP. They say that the DP solution is pseudo-polynomial, since it is exponential in the "length of input" (i.e. the numbers of bits required to encode the input). Unfortunately I did not…
Michael
  • 41,026
  • 70
  • 193
  • 341
33
votes
3 answers

0/1 knapsack with dependent item weight?

The standard 0/1 knapsack requires that the weight of every item is independent to others. Then DP is a efficient algorithm towards the solution. But now I met a similar but extensions of this problem, that the weight of new items are dependent on…
Paddy Xu
  • 518
  • 4
  • 8
25
votes
14 answers

Algorithm to Divide a list of numbers into 2 equal sum lists

There is a list of numbers. The list is to be divided into 2 equal sized lists, with a minimal difference in sum. The sums have to be printed. #Example: >>>que = [2,3,10,5,8,9,7,3,5,2] >>>make_teams(que) 27 27 Is there an error in the following…
lprsd
  • 84,407
  • 47
  • 135
  • 168
24
votes
2 answers

Memory-constrained coin changing for numbers up to one billion

I faced this problem on one training. Namely we have given N different values (N<= 100). Let's name this array A[N], for this array A we are sure that we have 1 in the array and A[i] ≤ 109. Secondly we have given number S where S ≤ 109. Now we have…
someone12321
  • 755
  • 5
  • 24
19
votes
4 answers

How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?

Here I have code which calculates the optimal value using the knapsack algorithm (bin packing NP-hard problem): int Knapsack::knapsack(std::vector& items, int W) { size_t n = items.size(); std::vector > dp(W + 1,…
prvit
  • 956
  • 3
  • 9
  • 22
19
votes
6 answers

Do you need to sort inputs for dynamic programming knapsack

In every single example I've found for a 1/0 Knapsack problem using dynamic programming where the items have weights(costs) and profits, it never explicitly says to sort the items list, but in all the examples they are sorted by increasing both…
Tommy K
  • 1,759
  • 3
  • 28
  • 51
18
votes
10 answers

How do I solve the 'classic' knapsack algorithm recursively?

This is my task The Knapsack Problem is a classic in computer science. In its simplest form it involves trying to fit items of different weights into a knapsack so that the knapsack ends up with a specified total weight. You don't need to fit…
lampShade
  • 4,361
  • 8
  • 34
  • 50
18
votes
4 answers

How does DP helps if there are no overlapping in sub problems [0/1 knapsack]

Consider below inputs for typical Knapsack problem. V = [10,8,12] W = [2,3,7] i = 1,2,3 C = 10 I tried recursion with memoization to solve this sample but found no overlapping sub problem. Signature of the recursive procedure : knapsack(int c,…
nits.kk
  • 5,204
  • 4
  • 33
  • 55
18
votes
5 answers

Multiple Constraint Knapsack Problem

If there is more than one constraint (for example, both a volume limit and a weight limit, where the volume and weight of each item are not related), we get the multiply-constrained knapsack problem, multi-dimensional knapsack problem, or…
EFreak
  • 3,119
  • 3
  • 27
  • 31
17
votes
2 answers

Knapsack - brute force algorithm

I have found this code to solve Knapsack Problem using brute force mechanism (this is mostly for learning, so no need to point out dynamic is more efficient). I got the code to work, and understand most of it. MOST. Here's the question: I've noticed…
Bartosz Cieszewski
  • 265
  • 3
  • 15
17
votes
3 answers

Optimal way of filling 2 knapsacks?

The dynamic programming algorithm to optimally fill a knapsack works well in the case of one knapsack. But is there an efficient known algorithm that will optimally fill 2 knapsacks (capacities can be unequal)? I have tried the following two…
Nikunj Banka
  • 11,117
  • 16
  • 74
  • 112
15
votes
2 answers

Variation on knapsack - minimum total value exceeding 'W'

Given the usual n sets of items (each unlimited, say), with weights and values: w1, v1 w2, v2 ... wn, vn and a target weight W, I need to choose items such that the total weight is at least W and the total value is minimized. This looks to me like…
ragebiswas
  • 3,818
  • 9
  • 38
  • 39
15
votes
5 answers

Efficient table for Dynamic Programming in Haskell

I've coded up the 0-1 Knapsack problem in Haskell. I'm fairly proud about the laziness and level of generality achieved so far. I start by providing functions for creating and dealing with a lazy 2d matrix. mkList f = map f [0..] mkTable f = mkList…
Dan Burton
  • 53,238
  • 27
  • 117
  • 198
14
votes
6 answers

DP algorithm for bounded Knapsack?

The Wikipedia article about Knapsack problem contains lists three kinds of it: 1-0 (one item of a type) Bounded (several items of a type) Unbounded (unlimited number of items of a type) The article contains DP approaches for 1. and 3. types of…
lithuak
  • 6,028
  • 9
  • 42
  • 54
14
votes
2 answers

How is this memoized DP table too slow for SPOJ?

SPOILERS: I'm working on http://www.spoj.pl/problems/KNAPSACK/ so don't peek if you don't want a possible solution spoiled for you. The boilerplate: import Data.Sequence (index, fromList) import Data.MemoCombinators (memo2, integral) main =…
Dan Burton
  • 53,238
  • 27
  • 117
  • 198
1
2 3
…
73 74