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.

learn more… | top users | synonyms

1
vote
2answers
42 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 ...
1
vote
0answers
56 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 ...
0
votes
0answers
60 views

Is this problem a knapsack problem?

I have the following problem. Maximize $\sum\limits_{m=1}^M\sum\limits_{n=1}^N x_{mn}$ subject to: $\sum\limits_{\substack{m^\prime=1\\ m^\prime \neq m}}^M\sum\limits_{\substack{n^\prime=1\\ ...
2
votes
0answers
26 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 ...
1
vote
1answer
192 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 ...
2
votes
1answer
887 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 ...
1
vote
3answers
384 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 ...
-6
votes
1answer
207 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 ...
3
votes
0answers
186 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 ...
0
votes
1answer
208 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 ...
3
votes
2answers
213 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 ...
2
votes
0answers
270 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 ...
3
votes
1answer
177 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 ...
2
votes
0answers
140 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 ...
15
votes
0answers
201 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, ...
1
vote
2answers
145 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 ...
7
votes
2answers
967 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) ...