All Questions
43 questions
4
votes
1
answer
246
views
Knapsack Problem: Find Top-K Lower Profit Solutions
In the classic 0-1 knapsack problem, I am using the following (dynamic programming) algorithm to construct a "dp table":
def knapsack(weights, values, capacity):
n = len(weights)
...
- 6,949
0
votes
1
answer
118
views
Knapsack dynamic programming - Why are below 2 codes (similar implementation) giving different answers for a test case?
I need to solve the below knapsack problem to maximize value while staying within the knapsack's weight W.
n is the number of items available
W is the weight capacity of knapsack
wt is the weight ...
- 21
1
vote
1
answer
2k
views
Knapsack with SPECIFIC AMOUNT of items from different groups
So this is a variation of the Knapsack Problem I came with the other day.
It is like a 0-1 Knapsack Problem where there are multiple groups and each item belongs to only one group. The goal is to ...
- 31
0
votes
2
answers
1k
views
knapsack problem using brute force method in python
I am applying the following code to obtain the max CBU. Can I also get the list of selected items in a knapsack? Here is my code
def knapsack(CBU, weight, Capacity):
return knapsacksolution(CBU, ...
- 3
-2
votes
1
answer
263
views
Minimize the cost while reaching minimum value
Given n items with ci cost and vi value with target value X, return the number of items such that the cost is minimized while the total value of the items reaches the target X.
To me, this sounds like ...
- 39
1
vote
1
answer
121
views
Pick subset of items minimizing the count of the most frequent of the selected item's labels
Problem
I want to pick a subset of fixed size from a list of items such that the count of the most frequent occurrence of the labels of the selected items is minimized. In English, I have a DataFrame ...
- 3,264
0
votes
0
answers
79
views
Convert this 0-1 knapsack recursive to top down?
I have written a knapsack recursive function and trying to convert it into top down.
Is the recursive function correct?
Can you help me convert it to top down?
# with memoization - assuming n ...
- 1
0
votes
1
answer
359
views
Implementing traceback table in knapsack 0/1 code
I am trying to implement a traceback table in my dynamic programming algorithm for the knapsack 0/1 problem. In my code I have set up a traceback table matrix but I am unsure how to fill in those ...
- 31
2
votes
1
answer
558
views
Knapsack problem with dynamic programming for investment portfolio and traceback
I am working on a python project utilizing the knapsack problem with dynamic programming to find the best investments based on how much money can be invested. So far I am able to come up with the best ...
- 31
1
vote
2
answers
188
views
list index out of range for knapsack problem without repetition
Problem introduction:
You are given a set of bars of gold and your goal is to take as much gold as possible into
your bag. There is just one copy of each bar and for each bar you can either take it ...
- 83
1
vote
1
answer
148
views
Python is | slower than or operator? [duplicate]
For this Leetcode question, it seems that if I use the following code, it will pass the online judge:
Given a non-empty array nums containing only positive integers, find if the array can be ...
- 1,759
-1
votes
1
answer
827
views
Multiple optimal solutions for 0/1 Knapsack problem
A 0/1 knapsack problem with a maximum capacity constraint can have more than one optimal solution yielding the same profit but with/without the same capacity. How can we generate the set of all ...
1
vote
1
answer
879
views
Knapsack Problem: Why do I need a 2 dimensional DP Matrix
I came across some classical Knapsack solutions and they always build a 2-dimensional DP array.
In my opinion, my code below solves the classical knapsack problem but with only a 1-dim DP array.
Can ...
- 11
1
vote
0
answers
284
views
Keep track of items in dynamic programming(similar to Knapsack problem)
Hello I'm trying to solve this dp problem: https://vjudge.net/problem/UVA-990
I'm able to solve the initial problem result using this code below:
I used recursion and a memo table arr to optimize the ...
- 33
-1
votes
1
answer
74
views
Dynamic Programming Knapsack [closed]
I'm trying to solve this problem however several testcases fail.
I'm using a memo table to called arr to optimize recursion.
What may I have done wrong?
s=list(map(int,input().split()))
n=s[0]
W=s[1]
...
- 33