knapsack-problem Questions
6
Solved
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 requ...
Magyar asked 27/12, 2010 at 12:19
10
Solved
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 wi...
Northeast asked 15/10, 2011 at 0:1
4
Solved
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.
Sig...
Jelene asked 18/8, 2016 at 19:49
6
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 ...
Ovi asked 24/4, 2015 at 17:14
3
Solved
I need some clarification from wikipedia: Knapsack, on the part
This solution will therefore run in O(nW) time and O(nW) space. Additionally, if
we use only a 1-dimensional array m[W] to store ...
Synergistic asked 22/6, 2013 at 2:10
3
Solved
This variation of the knapsack problem requires a minimum weight. The goal is to minimize the cost while achieving at least the minimum weight.
For example, we have 6 items with weights {1, 1, 1, 5...
Outmaneuver asked 12/12, 2020 at 2:4
5
Solved
This is a hard algorithms problem that :
Divide the list in 2 parts (sum) that their sum closest to (most) each other
list length is 1 <= n <= 100 and their(numbers) weights 1<=w<=250...
Candis asked 18/12, 2010 at 18:42
3
A space optimization for the 0/1 knapsack dynamic programming algorithm is to use a 1-d array (say, A) of size equal to the knapsack capacity, and simply overwrite A[w] (if required) at each iterat...
Seljuk asked 25/4, 2016 at 7:8
4
Solved
Here I have code which calculates the optimal value using the knapsack algorithm (bin packing NP-hard problem):
int Knapsack::knapsack(std::vector<Item>& items, int W)
{
size_t n = items...
Sexism asked 20/9, 2011 at 17:43
6
Solved
Is the following 0-1 Knapsack problem solvable:
'float' positive values and
'float' weights (can be positive or negative)
'float' capacity of the knapsack > 0
I have on average < 10 items, ...
Xeroderma asked 14/11, 2011 at 17:11
6
Solved
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 art...
Marsh asked 4/3, 2012 at 23:1
2
Solved
I'm looking to maximize the number of stars given a certain budget and max limit on the combination.
Example question:
With a budget of 500 euro, visiting only the maximum allowed restaurants or l...
Briones asked 28/11, 2019 at 17:50
2
Solved
Is there a algorithm to determine a knapsack which has an exact weight W? I.e. it's like the normal 0/1 knapsack problem with n items each having weight w_i and value v_i. Maximise the value of all...
Augmentation asked 2/12, 2017 at 14:5
3
Solved
Suppose you are a thief and you invaded a house. Inside you found the following items:
A vase that weights 3 pounds and is worth 50 dollars.
A silver nugget that weights 6 pounds and is worth 30 do...
Huff asked 20/4, 2014 at 18:33
3
Solved
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...
Adina asked 9/2, 2013 at 10:2
4
Solved
I am trying to a C++ implementation of this knapsack problem using branch and bounding. There is a Java version on this website here: Implementing branch and bound for knapsack
I'm trying to make ...
Ephemeron asked 16/7, 2012 at 4:19
3
Solved
input:
max_weight = 550
n = 4
x_i = [120, 175, 250, 150]
output:
2
// [[250, 175, 120], [150]]
My initial impression is that this looks very similar to a dynamic programming coin change/knapsac...
Butyraceous asked 8/8, 2017 at 16:37
3
Solved
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 prob...
Cirrus asked 10/8, 2016 at 8:37
3
I have obtained a proof that would discredit a generally held idea regarding the 0/1 knapsack problem and I'm really having a hard time convincing my self I am right because I couldn't find any thi...
Sixpack asked 27/7, 2017 at 18:19
2
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. S...
Toxoplasmosis asked 12/7, 2017 at 14:35
4
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 proble...
Amentia asked 1/12, 2009 at 17:12
2
Solved
I have a problem which is similar to the Knapsack problem, more specifically the multidimensional variation.
I have a bunch of objects which all have a cost, a value, and a category. I need to the...
Syd asked 31/3, 2017 at 17:16
6
I know how to solve knapsack 0-1 problem with dynamic programming approach, but I am having troubles figuring out which items to take without compromising the complexity of O(N * C) (N items,...
Bendicta asked 8/2, 2011 at 16:23
2
Solved
Firstly, i am a php newbie... so i still code and understand php procedurally. that said,
i have a collection of numbers (amount) stored in a database.
Question: Using PHP and mySQL,
Whats the...
Boaz asked 5/3, 2017 at 15:56
3
Solved
I have a linear programming problem where I'm trying to select from a number of binary resources to optimize value, basically a knapsack problem. The issue I'm having is that the different resource...
Datary asked 1/12, 2016 at 1:1
1 Next >
© 2022 - 2025 — McMap. All rights reserved.