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.
2
votes
1answer
34 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 ...
2
votes
1answer
43 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
163 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
74 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
137 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
110 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 ...
0
votes
0answers
82 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
139 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
99 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 ...
10
votes
0answers
111 views
Knapsack problem with many divisibility conditions
Let $S$ be a set of natural numbers. We consider $S$ under the divisibility relation, i.e. $s_1 \leq_d s_2 \iff s_1 \mid s_2$. Let
$\qquad \displaystyle \alpha(S) = \max \{|V| \mid V\subseteq S, ...
1
vote
2answers
120 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
444 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) ...
