Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [knapsack-problems]

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.

0
votes
0answers
29 views

Multiple Knapsack Problem, but with exact weight/capacity? (All knapsacks have to be filled completely)

I have a few knapsacks of given capacities. Also, much more items of given weights and values. As usual, items have to be put into knapsacks to maximize profit. What is different from a standard ...
-1
votes
0answers
19 views

Knapsack problem

How do I approach this problem? In this generalized knapsack problem you are given n items. Each item j has an associated weight wj and a value vj . Furthermore, items are categorized into k disjoint ...
0
votes
0answers
16 views

Multi Knapsack each with different constraints

It seems that there's no end to knapsack variations… here's the one I bumped into (at work): There are: N items, each with the usual value and weight properties. M bins, each with an upper ...
0
votes
2answers
30 views

What's the time complexity bound for the Knapsack with real weights?

Let's start with the formalism: Let $W$ be the total weight of our bag, $1,...,n$ be our elements, $w_1,...,w_n$ their corresponding weights, and $v_1,...,v_n$ their corresponding values. As is ...
0
votes
1answer
24 views

DP recurrence relations: Coin change vs Knapsack

Take: KP recurrence relation $ max { [v + f(k-1,g-w ), f(k-1,g)] } $ if w <= g and k>0 CCP recurrence relation $ min {[1 + f(r,c-v), f(r-1,c)]} $ if v <= c and r>0 I don't ...
0
votes
1answer
41 views

Oven cooking queue problem: need help to determine its nature

CS community! I'm more of a practical programmer than a computer scientist, so I need your help to find a solution (or at least point me into the right direction) to an extremely practical problem ...
1
vote
1answer
51 views

Solving the Knapsack problem in $O(v^*n^2)$, where $v^*$ is the maximum value of all $n$ items

For my study I am supposed to develop an dynamic programming algorithm which solves the following simplification of the Knapsack problem in $O(v^*n^2)$ time ($v^*$ is the maximum value of all elements)...
0
votes
1answer
107 views

Help writing a dynamic programming algorithm in English

It’s Friday night and you have $n$ parties to go to. Party $i$ has a start time $s_i$ end time $t_i$ and a value $v_i \ge 0$. Think of the value as an indicator of how excited you are about that party....
1
vote
2answers
138 views

Knapsack problem: equal profits

I am looking for references to efficient algorithms that solve knapsack problem where all profits are equal. More formal definition of the problem from a Wikipedia article on KPs: If all the ...
0
votes
0answers
25 views

knapsack type solution to the 8 queens problem

I'm new to learning programming, and came across this problem of placing 8 queens on a chessboard, such that no two queens are on the same row, column or diagonal; i.e. no two queens attack each other....
1
vote
2answers
69 views

Variant of the Knapsack Problem

I've got problem on integer programming, specifically with the following knapsack problem. I'd be happy to get some suggestions on how to solve the problem in a time efficient way. There are 120 ...
1
vote
0answers
20 views

Calculate maximum sum of nodes property with limit on distance being traversed between nodes in a given graph

Given is an undirected weighted graph with N nodes, with each node having a property/Value. Aim is to find the bestpath which maximizes the sum of the nodes property which can be visited given a ...
1
vote
1answer
21 views

Knapsack-type problem where the objective function is a ratio

I have a problem where I have a number of proposed initiatives each with a cost and payoff. I need to select a subset of these initiatives in order to maximize the ROI for the selected set as a whole ...
5
votes
0answers
68 views

Specific quadratic 0-1 knapsack problem solvable in linear time?

I am interested in a simple variant of the quadratic knapsack problem. Let $\{w_1, \ldots, w_n\} \in \{0,1\}$ be $n$ weights and $\{v_1, \ldots, v_n\} \in \mathbb{R}$ be $n$ values. Furthermore, ...
2
votes
2answers
374 views

Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value

GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T. This question is a simplification of ...
1
vote
1answer
27 views

How do I model this expression maximization problem as a Knapsack problem?

Given two arrays of the same length $n$: $A = \{a_1,a_2,\dots,a_n\}$, $B = \{b_1,b_2,\dots,b_n\}$, I have to maximize the following expression: $$\frac{a_{i_1} + a_{i_2} + a_{i_3}+ \dots + a_{i_k}}...
-1
votes
1answer
55 views

A question about a variant of a knapsack problem

I have the following problem: Let $q_1,\cdots,q_k$ be natural numbers $> 0$, $q := \sum_{1\le i \le k}{q_i}$ and $s_1,\cdots,s_k$ be positive $>0$ real numbers, and $S$ be a positive real number....
1
vote
0answers
42 views

Knapsack problem with additional conditions for data objects

I've been trying to theorize how to solve a certain type of problem for months now. Suppose you have a collection of $m$ pre-defined $(d+2)$-dimensional vectors like so: $$(v, s, m_1, \dots, m_{d})$$...
1
vote
1answer
295 views

Fantasy premier league dream team algorithm?

For those of you who are not familiar with FPL, here's a short version. You have players playing as either Goalkeeper, Defender, Midfielder or Forward. Each player has some price (either rounded to .5 ...
1
vote
3answers
82 views

Is there an $O(n^2)$ or $O(n^3)$ time algorithm to check if a number is a sum of $k$ elements of sorted array?

Let $A$ be a sorted array of $n$ positive integers (sorted in non-decreasing order, that is there can be equal consecutive elements). Can we check whether some positive integer $x$ is a sum of $k$ ...
0
votes
1answer
141 views

proof of correctness for greedy knapsack algorithm

I don't really understand why is statement 1 ≥ statement 2 in the attached picture. From what I understand the negative term in statement 2 must be greater than or equal the negative term in statement ...
1
vote
0answers
128 views

why knapsack problem is a NP complete?

I understand that knapsack problem is solved with dynamic programming in O(nW) time which is not polynomial but there is a greedy solution for knapsack problem which solves it with O(nLgn) time so how ...
1
vote
1answer
52 views

Relative order of values and weights in Knapsack

In knapsack problem, we have some items with some values and weights. We also have a knapsack with a specific capacity, and we intend to fill the knapsack with these items. The main objective of this ...
0
votes
0answers
39 views

Determining epsilon for knapsack problem solved with FPTAS

I want to solve the knapsack problem with FPTAS and two parameters $\varepsilon_1 <\varepsilon_2$ . I know that as long as we choose smaller epsilon we get more tight approximation but we pay with ...
1
vote
2answers
127 views

How to solve this very complicated assignment problem

A set of m items need to be placed into n stacks, where m > n. Each stack has z positions. An item has different widths when placed into different positions in a stack. The width of an item depends ...
2
votes
1answer
339 views

A Special Case of Multiple Choice Knapsack Problem: Is it NP-hard?

The multiple choice knapsack problem (MCKP) can be defined as follows: MCKP is known to be NP-hard in general. I have a special case of MCKP for which $N_i=\{1,2,\cdots,|N_i|\}$, for all $1\...
1
vote
0answers
160 views

A knapsack problem with variable knapsack size

I've come across this problem and I can't find a decent DP solution for it. Given an initial amount of money and a bunch of items to buy (where each item has a 'value' and 'price' assigned to it), ...
-1
votes
1answer
228 views

Knapsack progblem with two conditions

I want to create an algorighm (with dynamic programing) similar to 1/0 knapsack problem but, I have one extra condition isVegetable or isFruit. Assume we have N food items where we know ...
0
votes
1answer
66 views

Knapsack problem with diminishing prices

I wonder if the knapsack problem with diminishing prices is already studied? The problem is similar to the regular knapsack problem, except the price of each item is a decreasing function of the total ...
0
votes
1answer
114 views

Knapsack problem question

Based on this video, the tutor explains the knapsack problem with dynamic programming approach. One thing is not cleared in this video, which is my main question. All the values on the first row (...
0
votes
1answer
103 views

Psedu-polynomial Time : Conflict with the definition of input size

From wikipedia In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required ...
1
vote
1answer
293 views

Transforming a bounded knapsack to 0/1 knapsack

Could I transform a bounded-knapsack problem into a 0/1 knapsack problem using the following way-: Example: Lets says I have 3 types of items $n=3$ $p_j=\{10,15,11\}$ $w_j=\{1,3,5\}$ $b_j=\{6,4,2\...
1
vote
0answers
310 views

Solving a Rod Cutting Problem

I'm trying to come up with an algorithm for optimizing cutting a rod. Most of the examples I see online are for a stock of rod of a single length and optimizing the way to cut it up for max price. I ...
0
votes
1answer
128 views

Knapsack Problem with Vector Values

I am searching for information on a variant of the 0-1 Knapsack Problem I will call the Vector Knapsack Problem (VKP), which is basically the same as the standard KP except that the values being ...
1
vote
0answers
30 views

Can the standard knapsack problem be solved using LLL?

It is well-known that the Merkle–Hellman knapsack cryptosystem can be solved using the LLL algorithm. In the Merkle-Hellman knapsack cryptosystem, we're trying to find a solution $x_i \in \{0,1\}$ ...
0
votes
0answers
68 views

Does dynamic programming always add one item per sub-solution?

In the 0-1 knapsack problem, I am given a set of items with their weights and the weight that a knapsack can carry. The objective is to maximize the number of items I can carry subject to the fact ...
1
vote
3answers
216 views

Modification of dynamic programming for a knapsack problem

We have the following recursive function for the dynamic programming problem for a knapsack problem: \begin{align} V(i,w)=&max[ V(i-1,w), v_i +V(i-1,w-w_i)], \quad 1\leq i \leq n, 0\leq w \leq W \...
4
votes
2answers
501 views

Variation of knapsack problem

I have a menu of n items, with each item having a value. Given the total amount spent, I have to figure out all the possible combinations of items purchased. Example, I have three menu items: item 1: ...
0
votes
1answer
110 views

Matching 2 sets of items by price

I'm trying to solve the following problem in the most efficient way I can find. I want to trade my items for someone elses items, every item have a price and a value. I want to maximize the value of ...
1
vote
4answers
185 views

What are some concrete (near-)“worst-case” examples of subset-sum?

I've written a subset-sum solver. It outputs all subsets that sum to a given value, iteratively. I'm measuring its performance by the average amount of time taken per subset found. However, I suspect ...
1
vote
1answer
68 views

Getting output of dynamic programming, (contiguous sub array, box stacking)

I am attempting to output the largest stack of boxes given an input of a set of boxes. Currently I have an array called maxWeight that has the values of the boxes sorted from largest to smallest, this ...
1
vote
0answers
36 views

Classify the knapsack problem

Consider the following problem. Given a set of $n$ items having weight $w_i$ and value $v_i$ and a maximum capacity $W$, maximize $\sum\limits_{i=1}^n a _i v_i$ under $\sum\limits_{i=1}^n a_i w_i \leq ...
1
vote
0answers
180 views

With restrictions, can the knapsack puzzle be solved with a greedy algorithm?

I know that with the knapsack problem in general, there is no known greedy algorithm to solve it. But, say we add the following constraints: • All items have values equal to their weights (for all $...
2
votes
1answer
682 views

Multi- Knapsack problem variation

I'm trying to model a scenario where there are n items, each having weight and volume. We also have m number of knapsack, each ...
1
vote
2answers
171 views

Is a Knapsack Problem with only Color Constraints NP-Complete?

I have a knapsack problem that has been frustrating me for weeks, in which we consider a set of n items, described by their integer value, and being of one of C colors. There exists a constraint on ...
2
votes
0answers
104 views

Is there a pseudo polynomial time algorithm for this 0-1 quadratic subset sum problem?

Say that we have some (integer) weights $w_{1,1},w_{1,2},...,,w_{m,m}$ and a target sum $W$. Suppose that we want to find whether there are $a_1,...,a_m \in \{0,1\}$ such that $$\sum_{i = 1}^{m} \...
1
vote
1answer
260 views

SAT to knapsack vs. ETH

Theorem states that every problem in $\mathsf{NP}$ can be reduced to another $\mathsf{NP}$-complete problem in polynomial time. Also you can only make a problem polynomially longer using polynomial ...
2
votes
1answer
767 views

01 Knapsack with selection of items with minimum total weight

I have a slightly modified version of a classical 01 knapsack problem. Specifically, the problem has an additional constraint which requires that if more than one feasible selection with equal value ...
1
vote
1answer
91 views

Multi-dimensional Knapsack with added one-per-group constraint

I have some sets (A, B, ...) each containing some vectors (e.g. [1, 0, -1]). How can I pick exactly one vector per set such that they sum to a specified target vector? For example: ...
0
votes
1answer
65 views

Algorithm to find the optimal strategy to feed your cousin (Long question)

I have a programming problem, instead of describing the whole domain it's easier for me to create an analogy. The numbers I use in this example are completely arbitrary. Your cousin is coming over ...