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.

Filter by
Sorted by
Tagged with
2
votes
0answers
520 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
451 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
161 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
81 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 ...
2
votes
3answers
422 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
3k 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
154 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
513 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
92 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
110 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
383 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 $...
3
votes
1answer
2k 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 ...
0
votes
2answers
275 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
143 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
524 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
2k 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
210 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
88 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 ...
2
votes
1answer
4k views

Multiple Knapsack using Dynamic Programming

Def MKP (Multiple Knapsack Problem): Given a set of n items and a set of m bags (m <= n), with pj: profit of item j wj: weight of item j ci: capacity of bag i select m disjoint subsets of items ...
0
votes
1answer
182 views

what is approach of solving MINUS on SPOJ?

Link: http://www.spoj.com/problems/MINUS/ I have an Idea, after doing n-1 operations one can see that there is just + and - coefficients before each number that matters. For eg. given sequence: 12 ...
0
votes
1answer
935 views

Knapsack problem with the restriction on the number of items

Suppose $X$ is a set of integers. I am interested in the algorithm which computes the number of ways to represent an integer $W$ as a sum of exactly $k$ elements from $X$. Is it possible to modify the ...
0
votes
0answers
318 views

Variation on Multiple-Choice Multi-Dimensional knapsack problem (MMKP)

The Multiple-Choice Multi-Dimensional knapsack (MMKP) problem is defined as follows. The input is $N$ groups of items, each item in each group has a value, and requires $m$ resources. The total ...
1
vote
2answers
139 views

minimize sum of primes with a lower bound on product

I can't quite figure out an algorithm for this: Given some integer n, what subset of the primes (so no repeats) would yield the lowest possible sum if their product is at least n? Example: 6 -> 2*3, ...
0
votes
0answers
19 views

The 0-1 Knapsack problem - Regression equation [duplicate]

I'm trying to figure out the regression equation for the 0-1 Knapsack problem recursive algorithm: ...
0
votes
1answer
301 views

Prove that my NP-complete problem is strong

I have two problems, one of which is solved using dynamic programming. I showed that it is NP-complete (a knapsack variant), therefore having this dynamic programming solution says that this one is ...
1
vote
1answer
110 views

Which algorithm suits this problem best?

I have an optimization problem and I'm looking to find an algorithm whitch best fits this. The problem is the following: There are several points of interest (POI), each has a value (for the user), ...
0
votes
1answer
5k views

Difference between fractional knapsack & greedy solution

I am trying to understand what the difference is between the fractional knapsack problem using dynamic programming, and the greedy solution version. Im looking at an example of the fractional problem ...
1
vote
0answers
88 views

Bin Packing across multiple iterations

I am working with an iterative application in a distributed setup. The application has n processes (P1, P2,...Pn) and m iterations. Each process may or may not perform any computation in a given ...
1
vote
1answer
60 views

Can such an algorithm be written using recursion

I'm writing an algorithm that, given a limit N, and given a list of elements of value V, find all the possible combinations so ...
1
vote
0answers
29 views

Is there any knapsack-based cryptosystem that hasn't been broken?

I took part in the development of a knapsack-based asymmetric cryptosystem, and am currently planing to launch a campaign to promote it. Before we actually do, it occurred to me to research... what ...
0
votes
1answer
981 views

Is knapsack a Linear Programming problem? [closed]

Since Knapsack give Optimal solution as LP so is it also a LP or not ?
2
votes
1answer
315 views

Why there is no FPTAS for multiple knapsack problem for two knapsacks unless P=NP?

The multiple knapsack problem (MKP) is defined in "A PTAS for the Multiple Knapsack Problem" as: Instance: A pair $(B, S)$ where $B$ is a set of $m$ knapsacks and $S$ is a set of $n$ items. Each bin $...
4
votes
2answers
171 views

Smallest cost in weighted directed graph with combinations

I am trying to develop an algorithm that can traverse a graph with intermediary/all or nothing(?) nodes. The problem is that there are companies B, C and D that are bidding on projects X, Y and Z. ...
-2
votes
1answer
537 views

How to prove this “np-complete” problem?

I have a problem that I need to prove its np-completness: My original question I need to reduce it from some problem, i´m trying to do it from some other than knapsack, that´s why I ask again. I need ...
1
vote
0answers
366 views

Reducing a problem with two knapsack that needs equal number of items from Knapsack?

I am trying to reduce a Knapsack problem to a problem I need to solve, and I am suspicious of its NP-Completness. The problem recieve an array of elements $v_1,v_2,...,v_n$ sorted in some order from ...
0
votes
1answer
65 views

How can i fill shelves with products so that I have the maximum amount of sales?

I have to do a project where I write a greedy algorithm to maximize a company's sales. There are 6 shelves, each with 8m length. I have to position 100 items whose length, value and max sales ...
5
votes
2answers
597 views

Version of knap sack problem

The are cuisenaire rods with N differnt lengthes $x_1,x_2,...,x_n$ (each length is a natural number), the number of the Cuisenaire rods is unlimited. Given a natural number B. you should tell if you ...
0
votes
1answer
285 views

Knapsack variant

In my line of work, I have encountered the following variant of discrete knapsack and I was wondering if it has already been studied. E.g. We are given a set of 3 items (A,B,C). The goal is to ...
3
votes
3answers
329 views

Contained optimal combination of inputs

I have 100 football (soccer) players, each with an "expected score" (higher is better) and price (e.g. 4300 dollars). I want to select the optimal combination of players with the highest combined ...
2
votes
2answers
439 views

Knapsack and set cover-like problem

Given $n$ sets $r_1, r_2, \cdots, r_n$ and a number $\delta$ where $0 \le \delta \le 1$. Let $T=\cup_{i=1}^{n}r_i=\{t_1,t_2,\cdots,t_m\}$. Each $t$ has a value $v(t)$, which is given to us. The task ...
0
votes
1answer
677 views

A special case for the subset sum problem: selecting from powers of two

Given a multiset $X=\{x_1,\dots,x_n\}$ where every element $w_i$ is a power of two, and given an integer $M$, I'd like to determine if there is any subset of $X$ that sums to $M$. (This question is ...
2
votes
1answer
550 views

A special case for the subset sum problem

If we wanted to see if any disjointed subset of a set $X = [w_1, ..., w_n]$ exists such as the sum of its elements equal exactly a given value $M$ (0-1 Knapsack problem) we could employ a DP solution ...
2
votes
0answers
211 views

Is there a name for the knapsack problem with no bound on knapsack capacity?

I am investigating heuristics for optimising the packing a fixed number of knapsacks with a set of items of defined weights, however the knapsacks do not have a defined capacity limit. The objective ...
1
vote
2answers
5k views

Multiple Constraint Knapsack Problem Dynamic Programming

Is there any way for solving the Knapsack problem when we are limited by several constraints? Let's assume that we have a set of items in which we have value v ...
2
votes
0answers
118 views

One variant of the Knapsack Problem

We have a normal knapsack problem but we can choose up to $t_i$ of the $i$-th object. How would you solve this problem with complexity less than $O(V(n + \sigma(t_i)))$ where $n$ is number of objects ...
4
votes
0answers
121 views

Complexity of a non-linear knapsack problem

Minimize $$\sum_{i=1}^{n}\sum_{j=1}^{m_i}w_{i,j}v_{i,j}$$ subject to $$\sum_{i=1}^{n}\frac{m_i}{m_i+\sum_{j=1}^{m_i}v_{i,j}} < \theta$$ $$v_{i,j}\in\{0,1\}~\forall i,~j$$ where $w_{i,j}$ and ...
4
votes
0answers
263 views

Subset sum with wider constraint

The classical 0,1 knapsack problem with weights $w$ and unit value for all items $x$: $ max \displaystyle\sum_{i} x_i, x_i \in \{0,1\} $ subject to $ \displaystyle\sum_{i} w_ix_i \leq W $ for a ...
0
votes
1answer
64 views

Help me identify the type of Knapack Problem I am dealing with

I have a multiple knapsack problem I am trying to solve. To get the right solution, we need to ask the right question. My question is simply to identify what type of problem I have, not to solve the ...
1
vote
1answer
205 views

Solving an ordered knapsack problem exactly with a non linear (blackbox) evaluation function

Thanks in advance for the help. I have the following problem which, for lack of a better description, I'm referring to as the problem I've listed in the title. Specifically I have a knapsack problem ...
7
votes
1answer
1k views

Knapsack with same value

I'm wondering if there's a name/reference for the variant of knapsack problem where all items have the same value (so we only care about maximizing the number of items), but there are multiple weight ...