Questions tagged [knapsack-problem]

The knapsack problem is a problem in combinatorial optimization: Given a set of items with associated weights and values, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and it maximizes the total value. It is an NP-complete problem, but several common simplifications are solved efficiently with dynamic programming.

Filter by
Sorted by
Tagged with
3 votes
1 answer
74 views

Spell casting - How to optimize damage per second : Variation of 0-1 Knapsack [closed]

I am trying to make an algorithm that finds the sequence of spell that maximizes the total damage. I understood this situation as a 0-1 knapsack problem with cooldown for each item. However, I couldn'...
evol1102's user avatar
-4 votes
0 answers
18 views

How we can improve themselves? [closed]

The 0/1 Knapsack problem is a classic optimization challenge where the objective is to determine the most valuable combination of items to fit into a knapsack of limited capacity. The problem involves ...
Anisha Kumari's user avatar
0 votes
0 answers
12 views

Edge Addition: Item subset selection problem (Knapsack?)

I have a set of n edges, e-star, which is the set of valid possible extra edges to an existing graph, G(v,e). I want to minimise the median route path length across the network from a central point, c,...
sploopst's user avatar
1 vote
0 answers
84 views

Get X and Y sizes of remaining surface area

I have bins that I'm packing components into, but have trouble with components of smaller sizes not "using" the available space in the current bin (so I am creating a new bin when it isn't ...
Parrotmaster's user avatar
0 votes
0 answers
33 views

knapsack optimization using Python pulp - how to set constraints?

I want to develop inventory fulfillment optimization model. I want to fulfil from Plt_Inv to WH_Inv if WH_Inv is less than SS for each SKUs, with total fulfillment volume should be less than 10000KG. ...
Sattai's user avatar
  • 1
0 votes
2 answers
103 views

Solving the Fractional Knapsack problem using Binary Search

The Fractional Knapsack Problem revolves around selecting items from a given set to fit into a knapsack of limited capacity. Each item has a weight and a value associated with it, and the goal is to ...
ShouryaSetu's user avatar
2 votes
2 answers
254 views

Find optimal combination of items with 2 values

I have a list of 500 elements each with 2 values x (float value from 0-Infinity) and a y (float value from 0-1). I need to find the cheapest (lowest sum(x)) combination of 10 of these elements that ...
caidora's user avatar
  • 23
1 vote
0 answers
74 views

Time complexity increased by using memoization when I use map<pair<int,int>,int> to store the DP state

I was solving the CSES-Apple Division Problem. It was a dp sum difference minimization problem. We have to divide an array into two subsets whose sum difference is minimum. I was using basic Recursion ...
Red_RanGer's user avatar
-1 votes
1 answer
29 views

knapsack code is not working in python while submitting it in GFG

I am trying to solve GeeksforGeeks problem 0 - 1 Knapsack Problem : You are given weights and values of N items, put these items in a knapsack of capacity W to get the maximum total value in the ...
Balbir singh's user avatar
0 votes
0 answers
12 views

How to solve algo trading bug

Following a course on algorithmic trading on python. However, 20 minutes in, run a command and get this. Please help. tried everything the code i ran. Everything is updated and I have tried everything....
Boris 's user avatar
0 votes
0 answers
13 views

With this minor change in the way of solution can't solve all the test cases (0-1 knapsack problem)

I was doing 0-1 knapsack problem with the help of dp but when I make a slight change in the code, I get a wrong answer in certain text cases - can't figure out why and I can't figure out how my logic ...
ionstone's user avatar
0 votes
0 answers
17 views

How to pack multiple items on fewest packs based on weight and type of item

So, I have N number of part types and each can have M number of members. Each type has a weight associated with it, and the packs have a weight limit. My job is to figure out how to both minimise the ...
Pedro Romero's user avatar
0 votes
0 answers
13 views

Please tell my error in this knapsack 0/1 problem

input first line:input is as follows here n is no. of element , W is max possible weight we can take. wi and vi are weights of individual element and their corresponding value. my code is as follows ...
abc123's user avatar
  • 1
0 votes
0 answers
31 views

This is a solution to the simplest knapsack problem but the result weight always exceeds the permitted amount

I'm trying to fix this for a whole night but still the program doesn't work, and I felt like there's nothing wrong with it. The list taken is responsible for recording the objects that's being carried ...
whiteSilence11's user avatar
1 vote
1 answer
102 views

Find a subset of a set of vectors such that the difference between the maximum and minimum element of the sum of the subset is minimal

The length of each vector is equal to 3. The number of vectors is no more than 300 and sum of the sum of all vectors is no more than 500. Example: For set of vectors: [0, 0, 1], [2, 3, 4], [0, 5, 0], [...
queue's user avatar
  • 11
0 votes
0 answers
38 views

Unbounded knapsack problem with extra reward for certain combinations

I am thinking about a variant of the unbounded knapsack problem, where extra value is added for certain combination of items. Suppose we have N items and the i-th item has value v_i and weight w_i. ...
lamc's user avatar
  • 347
3 votes
1 answer
84 views

Searching Algorithm: Product Knapsack Problem with goal to find lowest product above a certain threshold?

I'm looking for people with some algorithmic knowledge who can help me out with this. I'm currently programming a constrained tree search in java, where I want to have a certain amount of leaf nodes ...
ChomskyEnjoyer's user avatar
0 votes
0 answers
18 views

How to find the best combination of pairs in this particular problem?

I have a set of pairs of numbers each associated with a benefit. for example: (x,y)|benefit S={(2,3)|4,(4,5)|6,(6,7)|1,(8,9)|3} and let B(X) be a function that sum all the benefits in the set for ...
Raxreedoroid's user avatar
0 votes
0 answers
24 views

Python knap sack problem with recursion tree

Hello I have 5 blanks on the Python code below in bmax_val() and bfast_max() functions I'm trying to draw recursion tree as a result but it's too difficult to solve this problem I tried to put indent =...
CocaCola's user avatar
3 votes
1 answer
130 views

Comparison of BFS and DFS algorithm for the Knapsack problem

I am fairly new to python and I have a task which tells me to compare both algorithm time expended and space used in memory. I have coded both algorithms and ran them both. I was able to measure the ...
zellez's user avatar
  • 400
1 vote
1 answer
57 views

a ortools problem,find min value of the Knapsack problem,but value is caculated by tensorflow model not constant coefficient

public List<Waste> main(List<Waste> nowStock) throws Exception { Loader.loadNativeLibraries(); HashMap<@Nullable Integer, @Nullable Waste> iToWaste = Maps.newHashMap(); ...
冯佳奇's user avatar
0 votes
2 answers
56 views

Number of ways I can have as least M itens chosen from L itens (L >= M), where the price of all chosen S itens can't be greater than Q

L = number of given itens 0 < L < 31 P[j] = price of item j M = smaller quantity of items I must have Q = Greater quantity which can be spent Also, I can't have more than one item of each type. ...
Tomás Nascimento's user avatar
0 votes
1 answer
33 views

in my android studio every button working but when i use flatbutton its not working so what can i do now?

enter image description here please how can i use flat button now? I am trying to solve this and expected that someone will help me here.
Tanveer Syed's user avatar
0 votes
0 answers
50 views

Struggling to find the flaw in my logic for Fractional Knapsack problem (Maximum Value of the Loot)

This problem has been asked before: the problem however I have been struggling for a while to debug where my logic is wrong because my algorithm fails on this unknown test case: Failed case #7/13: ...
codinator's user avatar
-1 votes
1 answer
131 views

Do dynamic programming and branch and bound give same result when solving 0/1 knapsack problem?

Hi I have a question about knapsack problem and it's algorithms. I have built some code to solve 0/1 knapsack problem with Dynamic Programming and Branch and Bound. The value and weight are randomly ...
Ohtani King's user avatar
3 votes
2 answers
152 views

Multiple knapsack problem with no solution but finding a way to remove item(s) that are preventing a solution

I am trying to find a way to have as few boxes as possible that fit bags of chemicals. A box cannot have weight more than 3.3 kg but have to be higher than 2.7 kg. I came across Google's OR tools but ...
zoc99's user avatar
  • 105
0 votes
1 answer
32 views

shares of stack problem with js and dynamic programming

The problem receives an input like [[500, 5, 1], [450, 2, 1], [400, 5, 1]], where each row represents a buyer. Each buyer has a value in position 0, which represents the amount they are willing to pay ...
Nicolas Fredsny's user avatar
0 votes
0 answers
48 views

Knapsack DP returning incorrect answer

My memoized knapsack O/1 problem results in a smaller answer than expected for some test cases. Test case maxWeight = 1000 weights = [3,68,24,80,76,9,24,2,46,75,56,41,95,46,23,34,64,76,6,48,25,73,87]...
JohnySmith12's user avatar
0 votes
0 answers
70 views

0/1 Knapsack - return maximum value + list of included items - Top Down Approach - Time Complexity cubic or quadratic?

I am trying to solve the classic 0/1 knapsack problem with a slight variant where we are asked to return the maximum value + the list of included items. Input items = [[1,2],[4,3],[5,6],[6,7]] where ...
Zephyr's user avatar
  • 21
0 votes
0 answers
67 views

PHP Qty distribution with max value

I've been struggle on this problem over than 2 weeks, I've data like below : Someone told me it's should knapsack or anything, but I don't know how to do. Master Category Category Qty per Box P 12 ...
shev's user avatar
  • 1
1 vote
1 answer
51 views

Why does rank 14 output at the end of the first if statement even though it says if(rank == 0)?

I am trying to use MPI to develop a parallel solution in C to the NP-Complete Knapsack problem. When I run the code, the printf statement at the end of the first if statement outputs as rank 14, not ...
IrrationalPi's user avatar
0 votes
0 answers
19 views

Theoretical basis of the Knapsack problem

I cannot imagine how to develop the ideas about the theoretical basis of the Knapsack problem and also do not know any useful documents about it. I hope someone can help me. I would like to know how ...
Phan Thế Hoàng's user avatar
0 votes
1 answer
168 views

Solving Knapsack Problem for large dataset using PULP library in Python

I have the below dataframe: import itertools import pandas as pd import numpy as np p1_values = np.arange(19, 29.1, 0.1) p2_values = np.arange(23, 33.1, 0.1) p3_values = np.arange(36, 46.1, 0.1) ...
Manny's user avatar
  • 63
0 votes
1 answer
39 views

Java Collection with multiple keys that refer to a different value that is also sortable (by key and index)

I had a lot of problems with my program recently, as I am not able to create a Collection which has duplicate keys at the same that refer to a different value. It's like an array in a List. I already ...
Glandorf's user avatar
3 votes
1 answer
81 views

Filling two fractional knapsacks using the same items

I have two knapsacks, let's call them knapsack A, and knapsack B, each knapsack has a max weight limit. We also have some item types that we can take with us. Each item type has a price, and two ...
adamsass's user avatar
0 votes
0 answers
119 views

Solving 0-1 knapsack problem using memoization

Although I managed to get the correct output for a 0-1 knapsack problem, I'm still partially confused about how the code functions. This is my code: memo = {} def knapsack(weights, prices, capacity, ...
markadodo's user avatar
0 votes
0 answers
130 views

Can I add variables to a 2D knapsack problem that can take multiple values?

this is my first question on stack overflow and I am quite new to OR, so bear with me. I am trying to solve what could be considered a rectangular 2D knapsack problem with a twist. In order to solve ...
Felix Burmester's user avatar
0 votes
1 answer
100 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 ...
Malyada N's user avatar
0 votes
0 answers
25 views

Matching products to best-suited transportation boxes algorithm?

A set of products (p) P = {{100 100 20}, {120 200 27},... } is given as an array of dimensions {{lentgh_1 wide_1 height_1},{lentgh_2 wide_2 height_2},...} for each product. In total the number of ...
care_don_t's user avatar
0 votes
0 answers
41 views

How to create Chromosomes and Fitness function for this NP-Hard Genetic algorithm problem

Hi i am very new to genetic algorithm and i am stuck with this problem: A move is provided for a student. He has to store his things in small plastic boxes in a cardboard box with a capacity of 2 ...
QTARO's user avatar
  • 1
1 vote
2 answers
199 views

Knapsack problem: choose 5 elements among 100, weight <= 100, maximise total value

I have a data table containing n=100 elements : Element weight value A 24 80 B 43 77 C 51 72 D 38 70 E 27 65 F 7 58 .. .. .. And I would like to create an algorithm to get 5 elements where : ...
gnozer44's user avatar
0 votes
1 answer
34 views

my knapsack code does not work in python 3 can anyone help what is the problem with my code?

def knapSack(W, wi, pi, i): if i == 0 or W == 0: return 0 if (wi[i-1] > W): return knapSack(W, wi, pi, i-1) else: return max( pi[n-1] + ...
Sina sam sina_mix's user avatar
0 votes
0 answers
17 views

Quadratic profits depend on multi items rather than every two items of Quadratic Multi Knapsack Problem

There are multiple knapsacks that need to be filled exactly. Each knapsack has a different capacity. Items are unique. The weight of all items is 1.The value of item will be different when this item ...
learn's user avatar
  • 1
0 votes
1 answer
90 views

I got wrong output for 0/1 knapsack problem in python using backtracking

I implemented the 0/1 knapsack problem with the backtracking technique, but I didn't get the expected result. capacity : total knapsack capacity cargo_number : the number of items size : the weight ...
Asahisuki's user avatar
2 votes
1 answer
274 views

How to solve a Knapsack problem with extra constraints? (Or alternative algorithms)

Expanding upon a common dynamic programming solution for the knapsack problem: def knapSack(W, wt, val, n): results = [] K = [[0 for x in range(W + 1)] for x in range(n + 1)] # Build tаble ...
Olivia's user avatar
  • 814
-1 votes
1 answer
119 views

in knapsack problem, how do i know which items are taken?

i used dynamic programming to solve knapsack problem. #include <iostream> using namespace std; #define number 4 // number of item type typedef struct iteml { int itemw; // [weight of item] ...
RyuJin's user avatar
  • 1
0 votes
0 answers
66 views

Optimize appliances buy strategy according to discount on number of items

I'm going to buy some appliances from a shop and they offer the following discounts based on the number of items you buy: For 2 items the cheapest gets 25% off For 3 items the cheapest gets 55% off ...
drkg4b's user avatar
  • 377
1 vote
0 answers
508 views

How to solve the knapsack Problem when more than two properties of the Item are given (3 variables)

In the knapsack Problem how to solve it if one more property other than that of weight and value of the Item is given? Like recently I was asked a question where I was given 3 properties of the same ...
scarecrow's user avatar
0 votes
0 answers
31 views

Source containers constraints for assignment optimization in CVXPY

I am writing an assignment optimization (multiple knapsack) in CVXPY with multiple items from multiple source containers to multiple knapsacks. The items each have a value and there is another ...
Garrett Cheung's user avatar
1 vote
1 answer
866 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 ...
Pablo Roldán's user avatar

1
2 3 4 5
22