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.
246
questions
5
votes
2
answers
433
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 ...
- 51
1
vote
1
answer
446
views
How to make the standard DP algorithm for 0/1 Knapsack make larger steps?
The standard knapsack problem solution is O(nW) where we will increment the weight +1 at a time to get to the solution.
Is there any approach to the knapsack problem that does not require ...
- 113
5
votes
2
answers
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, ...
- 153
0
votes
0
answers
44
views
Algorithms for keeping number of backups constant
The problem is quite simple: backups are done at regular time intervals (with possible but rare exceptions). The storage however is not unlimited, and only a certain number of backups can be stored, ...
- 263
2
votes
1
answer
1k
views
Ordered knapsack problem?
I'm trying to find the name of this problem, and with it a reasonable algorithmic solution.
Setup: There are $n$ items with weights $w_1,\dots,w_n$, and $m<n$ buckets with target weights $a_1,\...
- 531
1
vote
1
answer
195
views
What makes an MILP problem solvable?
Knapsack problems, Assignment problems can all be expressed as (MILP) mixed integer linear programs. MILP is NP-complete. But Knapsack problem is solvable in pseudo-polynomial time using dynamic ...
- 153
5
votes
0
answers
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 ...
- 141
0
votes
0
answers
45
views
Complex 0/1 Backback Problem
Say I have 3 compartments in my backpack: red, green, blue and 3 sets of items: red items, green items and blue items which all have a weight and benefit. I also have a requirement around the total ...
- 101
10
votes
2
answers
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, ...
- 201
4
votes
1
answer
820
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 ...
- 657
1
vote
0
answers
131
views
FPTAS for knapsack with private valuations
The Knapsack problem has a well-known FPTAS based on rounding and then using the pseudopolynomial dynamic programming algorithm. When the valuations $v_i$ are private, we also need the assignment rule ...
- 375
0
votes
0
answers
95
views
Reducing a Knapsack-type problem to a known problem
The Quadratic Knapsack problem, introduced by Gallo, is an optimization problem in the following form:
$max \sum_{i=1}^n{\sum_{j=1}^n{q_{ij}x_ix_j}}$
$s.t \sum_{i=1}^n{w_ix_i} \leq c$
$x \in \{0, 1\...
- 141
0
votes
0
answers
605
views
Dynamic programming for counting knapsack solutions
Suppose the usual dynamic programming algorithm for the knapsack problem. If we swap the max with an addition, does the modified algorithm compute all the solutions with benefit $\leq W$? I ...
- 203
4
votes
0
answers
180
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)...
- 29.4k
2
votes
1
answer
50
views
Spandex knapsack?
I'm going camping. While I'm away, I plan to eat only s'mores, which consist of 20% chocolate, 50% marshmallow, and 30% graham cracker. I did a thorough clean-out of my pantry, which revealed multiple ...
- 143
2
votes
1
answer
217
views
Complexity of a knapsack variant
Consider the following traditional integer knapsack problem:
$\max \sum_{i=1}^k p_i \cdot x_i\\
\text{s.t.} \sum_{i=1}^k w_i \cdot x_i \leq W \\
x_i \in \{0,\ldots,k_i\} \text{ for each } i$
Now ...
- 622
-1
votes
1
answer
142
views
Limiting capacity of knapsack to a polynomial function of elements in the Knapsack problem
I saw somewhere that if we limit the capacity (weight) of the knapsack to a polynomial function of elements then the class of the problem changes to P, but it didn't say why. I can't figure out why is ...
- 131
2
votes
1
answer
471
views
Output of well-known algorithms for the Subset sum problem
According to Wikipedia:
In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set (or multiset) of integers, is ...
- 151
0
votes
1
answer
135
views
Extended knapsack: is it NP-complete? [closed]
I have a problem of this form coming from an application domain, similar to the classical knapsack problem but not quite the same:
Maximize the value of
($\sum_{i=1}^n v_i \cdot x_i) + B \cdot \frac{...
- 103
2
votes
1
answer
1k
views
Subset sum algorithm in O(n³ log n)?
I think that I have found an algorithm which resolve exactly the subset sum problem in $O(N^3)$ in the worst case, only for positive numbers.
After my research, I'm lost between all the algorithms ...
- 151
8
votes
1
answer
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 ...
- 211
2
votes
3
answers
17k
views
Brute force method to solve the 0-1 knapsack problem
I know that the brute force method is not the best way to solve the 0-1 knapsack problem. I'm not quite getting the dynamic programming idea, but would like to know the following:
If the brute force ...
- 203
-1
votes
1
answer
366
views
Solving a Variation of knapsack [closed]
I'm working on a problem which to me, seems very similar to a knapsack problem:
A furniture store is having sale: Purchase two items at the price of the more expensive one. David went to the store ...
- 175
4
votes
2
answers
1k
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 ...
- 839
-1
votes
1
answer
479
views
Unlimited Knapsack Problem
How would I solve the unbounded knapsack problem, only this time aiming to maximize the weight instead of the value?
- 143
5
votes
4
answers
4k
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 ...
user8722
2
votes
1
answer
565
views
Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?
According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved ...
- 213
5
votes
0
answers
159
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 ...
- 151
3
votes
1
answer
5k
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 ...
- 43
9
votes
1
answer
464
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 ...
- 29.5k
1
vote
3
answers
7k
views
Correctness proof of greedy algorithm for 0-1 knapsack problem
We have a 0-1 knapsack in which the increasing order of items by weight is the same as the decreasing order of items by value. Design a greedy algorithm and prove that the greedy choice guarantees an ...
- 235
1
vote
0
answers
437
views
Integer knapsack problem with bounded weights
Is there any literature about the complexity of the integer knapsack problem with bounded weights? To make it clear, I want an optimal solution to the following problem:
$\max \sum_{i=1}^k c_i \cdot ...
- 622
4
votes
0
answers
67
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 ...
- 41
11
votes
1
answer
15k
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 $...
- 113
3
votes
1
answer
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^...
- 269
8
votes
4
answers
10k
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 ...
- 89
-4
votes
1
answer
272
views
Maximizing profit
Problem:
Given 11 numbers
{N1,N2,N3,N4,N5,N6,N7,N8,N9,N10,N11}
where
N1:amount of profit from product A
N2:amount of profit from Product B
N3:amount of time ...
- 21
4
votes
0
answers
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 ...
- 325
0
votes
1
answer
2k
views
Knapsack problem with multiple constraints
I am unsure if I have even identified the problem correctly, but reading up on knapsack problem seems the closest to what I am trying to solve:
A cook has $k$ ingredients of $p$ quantities. Given a
...
- 101
4
votes
2
answers
1k
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 ...
- 141
6
votes
0
answers
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 ...
- 4,785
4
votes
1
answer
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 ...
- 1,027
4
votes
0
answers
316
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\...
- 6,171
28
votes
1
answer
724
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, ...
- 3,023
1
vote
2
answers
404
views
From FACTOR To KNAPSACK
If there were an algorithm that factored in polynomial time by means of examining each possible factor of a complex number efficiently, could one not also use this algorithm to solve unbounded ...
- 177
9
votes
2
answers
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) ...
- 621