Questions tagged [knapsack-problems]

A problem in combinatorial optimization. Given a set of items with both weight and value, determine the number of each item to include in a collection so that the total weight is at most a given limit and the value of the collection is maximized.

Filter by
Sorted by
Tagged with
28
votes
1answer
717 views

Subset sum problem with many divisibility conditions

Let $S$ be a set of natural numbers. We consider $S$ under the divisibility partial order, i.e. $s_1 \leq s_2 \iff s_1 \mid s_2$. Let $\qquad \displaystyle \alpha(S) = \max \{|V| \mid V\subseteq S, ...
11
votes
2answers
23k views

Why is the dynamic programming algorithm of the knapsack problem not polynomial? [duplicate]

The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack. Why is this not a polynomial-time ...
11
votes
1answer
14k views

Variant of the knapsack problem

How would you approach the knapsack problem in a dynamic programming situation if you now have to limit the number of item in the knapsack by a constant $p$ ? This is the same problem (max weight of $...
10
votes
2answers
4k views

Knapsack Greedy Approximation: Worst Case

I am currently studying approximation algorithms and I have run into an issue with a study problem. The approximation algorithm is for the general Knapsack problem, and it proposes a greedy approach, ...
9
votes
1answer
425 views

What algorithms exist for solving natural number linear systems?

I'm looking at the following problem: Given $n$-dimensional vectors of natural numbers $v_1, \ldots, v_m$ and some input vector $u$, is $u$ a linear combination of the $v_i$'s with natural number ...
9
votes
2answers
7k views

Algorithms for two and three dimensional Knapsack

I know that the 2D and 3D Knapsack problems are NPC, but is there any way to solve them in reasonable time if the instances are not very complicated? Would dynamic programming work? By 2D (3D) ...
8
votes
4answers
9k views

Find non-overlapping scheduled jobs with maximum cost

Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum. Now I'm not sure if a greedy algorithm will do the trick. That is, sort by ...
8
votes
1answer
6k views

Balanced Weight Distribution in Bins/Buckets

Let $W = \{w_1,w_2,...w_n\}$ be a set of integer weights. Let $B = \{b_1,b_2,...b_m\}$ be a set of buckets, with $m \leq n$. Let $T(b_j)$ represent the total weight present in bucket $b_j$, which is ...
7
votes
1answer
1k views

Knapsack with same value

I'm wondering if there's a name/reference for the variant of knapsack problem where all items have the same value (so we only care about maximizing the number of items), but there are multiple weight ...
6
votes
0answers
2k views

Relations between the knapsack problem, the bin packing problem, and the set packing problem?

I wonder what relations are between the knapsack problem, the bin packing problem and the set packing problem? From their mathematical formulations, I don't see the first two belong to the third one ...
5
votes
2answers
69 views

Detecting conservation, loss, or gain in a crafting game with items and recipes

Suppose we're designing a game like Minecraft where we have lots of items $i_1,i_2,...,i_n\in I$ and a bunch of recipes $r_1,r_2,...,r_m\in R$. Recipes are functions $r:(I\times\mathbb{N})^n\...
5
votes
2answers
1k views

Find 8 numbers whose sum is closest to a defined value

I have a file that has a number (a positive integer) on each row. Given a number $q$, I want to find a value that's a sum of some 8 numbers in the file, and is as close to $q$ as possible. So, ...
5
votes
2answers
584 views

Version of knap sack problem

The are cuisenaire rods with N differnt lengthes $x_1,x_2,...,x_n$ (each length is a natural number), the number of the Cuisenaire rods is unlimited. Given a natural number B. you should tell if you ...
5
votes
2answers
354 views

How can I efficiently find the optimal order to apply special offers to a shopping cart?

Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the ...
5
votes
0answers
100 views

Specific quadratic 0-1 knapsack problem solvable in linear time?

I am interested in a simple variant of the quadratic knapsack problem. Let $\{w_1, \ldots, w_n\} \in \{0,1\}$ be $n$ weights and $\{v_1, \ldots, v_n\} \in \mathbb{R}$ be $n$ values. Furthermore, ...
5
votes
0answers
605 views

2 Dimensional Subset Sum: looking for information

I do not know if this problems exists with a different name, if it is, I could not find it. The problem is this: Given a set $S$ of $n$ points in $\mathbb{Z}^2$, is there a subset $A\subset S$ ...
5
votes
0answers
2k views

Time Complexity of a Knapsack-derived problem

Consider the following problem: Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a ...
5
votes
0answers
155 views

Rate Pooling Optimization Algorythim

I have thousands of wireless LTE hotspots. Each month I need to assign each hotspot a rate plan. Each hotspot uses some amount of data in a month (represented in megabytes). Each rate plan has some ...
4
votes
4answers
3k views

Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?

On the wikipedia page for the knapsack problem it says that the runtime is $\mathcal{O} (nW)$ and goes on to say that this doesn't violate its classification as NP because the input size is related to ...
4
votes
2answers
170 views

Smallest cost in weighted directed graph with combinations

I am trying to develop an algorithm that can traverse a graph with intermediary/all or nothing(?) nodes. The problem is that there are companies B, C and D that are bidding on projects X, Y and Z. ...
4
votes
1answer
2k views

The running time of the knapsack problem is $O(n\cdot \min(B,V))$ and is not polynomial, why?

My question is why the dynamic programming of the knapsack problem does run in polynomial time? The question is answered here Why is the O(nW) algorithm for the Knapsack problem not a polynomial one? ...
4
votes
2answers
822 views

What's the big deal with the knapsack problem?

In my CS course, we are covering things from one topic to another in sort of a sensible manner. For example, binary search tree -> 234-tree -> red-black tree -> heap -> greedy algorithms -> dynamic ...
4
votes
2answers
211 views

Two recurrences for the change-making problem with repetition

The change-making problem with unbounded repetition is: Input: Unlimited quantities of coins with values $x_1, \ldots, x_n$ and an amount $v$. Output: Can the given $v$ amount of money be made ...
4
votes
1answer
1k views

Adjacent house , dynamic programming problem

I have to be honest this is a homework problem, but I just need to discuss this with some one. The problem is there is a row of n houses, with different profit e.g profit1 for house 1, it can be ...
4
votes
1answer
108 views

Still not understanding why the Knapsack Problem does NOT have a polynomial-time solution

All the explanations for why the $O(nW)$ DP algorithm that solves the Knapsack Problem is NOT polynomial repeat the same thing: it is the length (in bits) of the input that matters, not its value/...
4
votes
2answers
977 views

Algorithm to pack any small boxes into a big box

I have a container with a certain dimension. A number of small boxes that may be different in size is to be packed into the container. How to arrange the small boxes such that the container contains ...
4
votes
2answers
3k views

Variation of knapsack problem

I have a menu of n items, with each item having a value. Given the total amount spent, I have to figure out all the possible combinations of items purchased. Example, I have three menu items: item 1: ...
4
votes
1answer
3k views

Proof of 0/1 knapsack optimal substructure

I'm trying to understand why exactly the 0/1 knapsack problem actually has the optimal substructure property. Let $E$ be the set of items to consider and $v$ and $w$ the value and weight functions ...
4
votes
1answer
269 views

Counting the solutions to a restricted 0-1 knapsack problem

Consider the counting knapsack problem $\mathsf{\#IDKNAP}$ : Input: $n \in \mathbb{Z_+}$, $s \in \mathbb{Q}_+$, where $s$ is represented by a fraction $\frac{p}{q}$ in its lowest terms. Output: ...
4
votes
1answer
722 views

Making a branch-and-bound algorithm more efficient for a large input

I am trying to implement the branch and bound algorithm to solve the knapsack problem (in the Coursera discrete optimisation course). I tried implementing dynamic programming first, and that worked ...
4
votes
0answers
121 views

Complexity of a non-linear knapsack problem

Minimize $$\sum_{i=1}^{n}\sum_{j=1}^{m_i}w_{i,j}v_{i,j}$$ subject to $$\sum_{i=1}^{n}\frac{m_i}{m_i+\sum_{j=1}^{m_i}v_{i,j}} < \theta$$ $$v_{i,j}\in\{0,1\}~\forall i,~j$$ where $w_{i,j}$ and ...
4
votes
0answers
257 views

Subset sum with wider constraint

The classical 0,1 knapsack problem with weights $w$ and unit value for all items $x$: $ max \displaystyle\sum_{i} x_i, x_i \in \{0,1\} $ subject to $ \displaystyle\sum_{i} w_ix_i \leq W $ for a ...
4
votes
0answers
1k views

can we solve dynamic knapsack problem using Memoization approach?

As we know Dynamic programming has two techniques. Bottom up dynamic programming approach. Top down memoization approach Normally dynamic knapsack problem is solved using Bottom up dynamic ...
4
votes
0answers
168 views

Heuristics and libraries for the knapsack problem

A student of mine is studying the knapsack problem (0-1 with a single objective). She is also talking to an industry partner who has realistic problems she can try solving (between 1000 to 10000 items)...
4
votes
0answers
62 views

Adversarial bin packing

An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$). The ...
4
votes
0answers
1k views

Dynamic Knapsack Problem - Algorithms and References

I don't know the right name for this problem, or if there is a name, but it is inspired by my initial interpretation of the title of this question (my question is very different, so the link may be ...
4
votes
0answers
269 views

Reduction from knapsack problem to Integer relation that equals one

My question is related to the Integer Relation Detection Problem which can be formulated as: $\qquad a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0$ Where $\forall i. a_i\in\mathbb{Z} \land a_i<c \land x\...
3
votes
1answer
4k views

Dynamic Programming Solution to 0,1 KnapSack Problem

I am trying to understand the DP solution to the basic knapsack problem.However even after reading through a variety of tutorials ,its still beyond my comprehension.I am taking an algorithmics course ...
3
votes
2answers
320 views

Minimize a sum with a weight constraint

We are given N sets, each of which has a finite number of pairs $(x_i,y_i)$. $M_1=\{(0,0), (x_{1,1},y_{1,1}), ...\}$ ... $M_N=\{(0,0), (x_{1,N},y_{1,N}), ...\}$ ...
3
votes
1answer
104 views

Dynamic Programming - Thief Variation Probem

I've encountered a Dynamic Programming problem which is a variation of the thief one. Say you are a thief and you are given a number of houses in a row you should rob : $$House_1,House_2 \dots ...
3
votes
1answer
41 views

Non-existence of approximation algorithm for the knapsack problem

I am working on the following exercise: Prove that if $P \neq NP$, there cannot exist an approximation algorithm $A$ for the knapsack problem (KP) such that $\exists k \in \mathbb{N}, \forall I \in S: ...
3
votes
3answers
326 views

Contained optimal combination of inputs

I have 100 football (soccer) players, each with an "expected score" (higher is better) and price (e.g. 4300 dollars). I want to select the optimal combination of players with the highest combined ...
3
votes
1answer
1k views

Optimizing NFL draft picks

I have a little problem I have been trying to solve for a hobby after a friend got me interested in fantasy football: given a list of players, positions for those players, projected points, salary, ...
3
votes
4answers
142 views

Divide $n$ gifts among three people so as to minimize the difference in the total cost of gifts between the most lucky and the most unlucky people

Divide $n$ gifts of different values among three people so as to minimize the difference in the total cost of the gifts for the most lucky and the most unlucky persons. The total value of $n$ gifts ...
3
votes
1answer
2k views

Multi- Knapsack problem variation

I'm trying to model a scenario where there are n items, each having weight and volume. We also have m number of knapsack, each ...
3
votes
1answer
5k views

Confusion related to time complexity of dynamic programming algorithm for knapsack problem

I have this confusion related to the time complexity of the algorithm solving the knapsack problem using dynamic programming I didn't get how the time complexity of the algorithm came out to be $O(nV^...
3
votes
0answers
162 views

Finding all feasible solutions to a multiple-knapsack program

How can I find all feasible solutions to a 0-1 integer program that I have based on a knapsack-style problem? I have $n$ items and $m$ knapsacks. Each knapsack has a space limitation and each item ...
3
votes
0answers
134 views

Split a graph into 2 components with known distribution?

I'm trying to find a method to randomly split a connected planar graph $G$ into two connected components, such that the sum of the weights of vertices in each component are relatively close. (If there ...
3
votes
0answers
970 views

Finding the n-best items in a 0/1 Knapsack

I'm trying to understand why an alternate formula for finding the best $p$ items in a 0/1 knapsack with $n$ items isn't working. The formula was proposed by @Carlos Linares López in this answer: ...
2
votes
1answer
307 views

Why there is no FPTAS for multiple knapsack problem for two knapsacks unless P=NP?

The multiple knapsack problem (MKP) is defined in "A PTAS for the Multiple Knapsack Problem" as: Instance: A pair $(B, S)$ where $B$ is a set of $m$ knapsacks and $S$ is a set of $n$ items. Each bin $...

1
2 3 4 5