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.

learn more… | top users | synonyms

-3
votes
0answers
24 views

Knapsack big O probelm [on hold]

Knapsack problem: Given a set of n items, each with a weight and a value, the problem is to determine the number of these items to include in a knapsack such that the total weight is less than or ...
1
vote
0answers
27 views

Solving a Knapsack problem with a special structure

I have a set of $N$ items to fill a knapsack with maximum capacity $W$ and the maximum number of items that the knapsack can carry is $N_{m}$ items. The problem can be formulated as following: max ...
1
vote
1answer
18 views

Proof of 0/1 knapsack optimal substructure

I'm trying to understand why exactly the 0/1 knapsack problem actually has the optimal substructure property. Let $E$ be the set of items to consider and $v$ and $w$ the value and weight functions ...
1
vote
1answer
23 views

Why is OPT at least the most valuable item for FPTAS Knapsack?

In all the presentations of an FPTAS for Knapsack I've seen, it is asserted that the optimal value is at always at least the value of the maximum-valued item (e.g. here, slide 12, where we have $V ...
1
vote
1answer
50 views

What type of knapsack problem is this?

I need to choose the highest value combination of items given a specific set of constraints. These constraints are: Exactly 6 items from group A and 2 items from group B must be selected. Items in ...
0
votes
0answers
20 views

Extending the Knapsack Problem - Value of complementary items

I'm looking for literature related to the following combinatorial optimization problem, which can be generalized to other applications too. I'm wondering what people's thoughts are on how to approach ...
3
votes
2answers
122 views

Minimize a sum with a weight constraint

We are given N sets, each of which has a finite number of pairs $(x_i,y_i)$. $M_1=\{(0,0), (x_{1,1},y_{1,1}), ...\}$ ... $M_N=\{(0,0), (x_{1,N},y_{1,N}), ...\}$ ...
1
vote
2answers
93 views

Analysis of the following integer program

So the knapsack problem has an integer programming formulation as follows, $$ \max_x v\cdot x\\s.t \\x_i \in \{0,1\}\\w\cdot x \leq C$$ Now consider the second integer program which might be a ...
6
votes
2answers
688 views

Why is the dynamic programming algorithm of the knapsack problem not polynomial? [duplicate]

The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack. Why is this not a polynomial-time ...
2
votes
0answers
67 views

Problem related to the Knapsack problem: Is it NP-hard?

I am trying to know whether the following problem is NP-hard: Input: A positive number $k$ and $N$ pairs of numbers. Each pair $i$, contains the positive numbers $a_i$ and $b_i$. The problem is to ...
1
vote
1answer
130 views

Use dynamic programming to find a subset of numbers whose sum is closest to given number M

Given a set $A$ of $n$ positive integers $a_1, a_2,\ldots, a_n$ and another positive integer $M$, I'm going to find a subset of numbers of $A$ whose sum is closest to $M$. In other words, I'm trying ...
3
votes
1answer
91 views

Optimizing NFL draft picks

I have a little problem I have been trying to solve for a hobby after a friend got me interested in fantasy football: given a list of players, positions for those players, projected points, salary, ...
2
votes
0answers
53 views

Aprroximation scheme for Multiple Choice Knapsack

In the paper FAST APPROXIMATION ALGORITHMS FOR KNAPSACK PROBLEMS (E Lawler 1979) gives a FPTA( Fully Polynomial time Approximation ) for multiple choice knapsack problem(MKP) . But MKP being strongly ...
4
votes
1answer
101 views

Counting the solutions to a restricted 0-1 knapsack problem

Consider the counting knapsack problem $\mathsf{\#IDKNAP}$ : Input: $n \in \mathbb{Z_+}$, $s \in \mathbb{Q}_+$, where $s$ is represented by a fraction $\frac{p}{q}$ in its lowest terms. Output: ...
1
vote
0answers
45 views

Knapsack Variation (Fixed amount, different types)

I'm trying to figure out a variation to the knapsack problem. The major difference is all objects have a type. For an example we can call them type A, B, C, D, and E. In addition to this we have to ...
2
votes
0answers
56 views

Are there any algorithms to find top N possible knapsacks?

The classic knapsack problem is maximize $P^T X$ subject to $W^T X\le M$ for $P, W\in \mathbb{R}^d$ and $M\in \mathbb{R}$ and $X\in \{0, 1\}^d$. Is there any research into algorithms that find the top ...
3
votes
0answers
140 views

Finding the n-best items in a 0/1 Knapsack

I'm trying to understand why an alternate formula for finding the best $p$ items in a 0/1 knapsack with $n$ items isn't working. The formula was proposed by @Carlos Linares López in this answer: ...
1
vote
1answer
67 views

The running time of the knapsack problem is $O(n\cdot \min(B,V))$ and is not polynomial, why?

My question is why the dynamic programming of the knapsack problem does run in polynomial time? The question is answered here Why is the O(nW) algorithm for the Knapsack problem not a polynomial one? ...
2
votes
1answer
102 views

How can I efficiently find the optimal order to apply special offers to a shopping cart?

Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the ...
1
vote
1answer
51 views

How to make the standard DP algorithm for 0/1 Knapsack make larger steps?

The standard knapsack problem solution is O(nW) where we will increment the weight +1 at a time to get to the solution. Is there any approach to the knapsack problem that does not require ...
3
votes
1answer
140 views

Find 8 numbers whose sum is closest to a defined value

I have a file that has a number (a positive integer) on each row. Given a number $q$, I want to find a value that's a sum of some 8 numbers in the file, and is as close to $q$ as possible. So, ...
0
votes
0answers
29 views

Algorithms for keeping number of backups constant

The problem is quite simple: backups are done at regular time intervals (with possible but rare exceptions). The storage however is not unlimited, and only a certain number of backups can be stored, ...
1
vote
1answer
79 views

Ordered knapsack problem?

I'm trying to find the name of this problem, and with it a reasonable algorithmic solution. Setup: There are $n$ items with weights $w_1,\dots,w_n$, and $m<n$ buckets with target weights ...
1
vote
1answer
60 views

What makes an MILP problem solvable?

Knapsack problems, Assignment problems can all be expressed as (MILP) mixed integer linear programs. MILP is NP-complete. But Knapsack problem is solvable in pseudo-polynomial time using dynamic ...
5
votes
0answers
563 views

Time Complexity of a Knapsack-derived problem

Consider the following problem: Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a ...
0
votes
0answers
29 views

Complex 0/1 Backback Problem

Say I have 3 compartments in my backpack: red, green, blue and 3 sets of items: red items, green items and blue items which all have a weight and benefit. I also have a requirement around the total ...
1
vote
1answer
157 views

Knapsack Greedy Approximation: Worst Case

I am currently studying approximation algorithms and I have run into an issue with a study problem. The approximation algorithm is for the general Knapsack problem, and it proposes a greedy approach, ...
4
votes
1answer
144 views

Making a branch-and-bound algorithm more efficient for a large input

I am trying to implement the branch and bound algorithm to solve the knapsack problem (in the Coursera discrete optimisation course). I tried implementing dynamic programming first, and that worked ...
1
vote
0answers
30 views

FPTAS for knapsack with private valuations

The Knapsack problem has a well-known FPTAS based on rounding and then using the pseudopolynomial dynamic programming algorithm. When the valuations $v_i$ are private, we also need the assignment rule ...
0
votes
0answers
49 views

Reducing a Knapsack-type problem to a known problem

The Quadratic Knapsack problem, introduced by Gallo, is an optimization problem in the following form: $max \sum_{i=1}^n{\sum_{j=1}^n{q_{ij}x_ix_j}}$ $s.t \sum_{i=1}^n{w_ix_i} \leq c$ $x \in \{0, ...
0
votes
0answers
165 views

Dynamic programming for counting knapsack solutions

Suppose the usual dynamic programming algorithm for the knapsack problem. If we swap the max with an addition, does the modified algorithm compute all the solutions with benefit $\leq W$? I ...
5
votes
0answers
75 views

Heuristics and libraries for the knapsack problem

A student of mine is studying the knapsack problem (0-1 with a single objective). She is also talking to an industry partner who has realistic problems she can try solving (between 1000 to 10000 ...
2
votes
1answer
41 views

Spandex knapsack?

I'm going camping. While I'm away, I plan to eat only s'mores, which consist of 20% chocolate, 50% marshmallow, and 30% graham cracker. I did a thorough clean-out of my pantry, which revealed multiple ...
2
votes
1answer
89 views

Complexity of a knapsack variant

Consider the following traditional integer knapsack problem: $\max \sum_{i=1}^k p_i \cdot x_i\\ \text{s.t.} \sum_{i=1}^k w_i \cdot x_i \leq W \\ x_i \in \{0,\ldots,k_i\} \text{ for each } i$ Now ...
-1
votes
1answer
47 views

Limiting capacity of knapsack to a polynomial function of elements in the Knapsack problem

I saw somewhere that if we limit the capacity (weight) of the knapsack to a polynomial function of elements then the class of the problem changes to P, but it didn't say why. I can't figure out why is ...
2
votes
1answer
123 views

Output of well-known algorithms for the Subset sum problem

According to Wikipedia: In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set (or multiset) of integers, is ...
0
votes
1answer
31 views

Extended knapsack: is it NP-complete? [closed]

I have a problem of this form coming from an application domain, similar to the classical knapsack problem but not quite the same: Maximize the value of ($\sum_{i=1}^n v_i \cdot x_i) + B \cdot ...
1
vote
1answer
404 views

Subset sum algorithm in O(n³ log n)?

I think that I have found an algorithm which resolve exactly the subset sum problem in $O(N^3)$ in the worst case, only for positive numbers. After my research, I'm lost between all the algorithms ...
3
votes
1answer
503 views

Balanced Weight Distribution in Bins/Buckets

Let $W = \{w_1,w_2,...w_n\}$ be a set of integer weights. Let $B = \{b_1,b_2,...b_m\}$ be a set of buckets, with $m \leq n$. Let $T(b_j)$ represent the total weight present in bucket $b_j$, which ...
1
vote
2answers
3k views

Brute force method to solve the 0-1 knapsack problem

I know that the brute force method is not the best way to solve the 0-1 knapsack problem. I'm not quite getting the dynamic programming idea, but would like to know the following: If the brute force ...
-1
votes
1answer
104 views

Solving a Variation of knapsack [closed]

I'm working on a problem which to me, seems very similar to a knapsack problem: A furniture store is having sale: Purchase two items at the price of the more expensive one. David went to the store ...
3
votes
2answers
249 views

What's the big deal with the knapsack problem?

In my CS course, we are covering things from one topic to another in sort of a sensible manner. For example, binary search tree -> 234-tree -> red-black tree -> heap -> greedy algorithms -> dynamic ...
-1
votes
1answer
101 views

Unlimited Knapsack Problem

How would I solve the unbounded knapsack problem, only this time aiming to maximize the weight instead of the value?
4
votes
2answers
257 views

Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?

On the wikipedia page for the knapsack problem it says that the runtime is $\mathcal{O} (nW)$ and goes on to say that this doesn't violate its classification as NP because the input size is related to ...
2
votes
1answer
106 views

Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?

According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved ...
4
votes
0answers
99 views

Rate Pooling Optimization Algorythim

I have thousands of wireless LTE hotspots. Each month I need to assign each hotspot a rate plan. Each hotspot uses some amount of data in a month (represented in megabytes). Each rate plan has some ...
3
votes
1answer
1k views

Dynamic Programming Solution to 0,1 KnapSack Problem

I am trying to understand the DP solution to the basic knapsack problem.However even after reading through a variety of tutorials ,its still beyond my comprehension.I am taking an algorithmics course ...
1
vote
2answers
951 views

Correctness proof of greedy algorithm for 0-1 knapsack problem

We have a 0-1 knapsack in which the increasing order of items by weight is the same as the decreasing order of items by value. Design a greedy algorithm and prove that the greedy choice guarantees an ...
1
vote
0answers
122 views

Integer knapsack problem with bounded weights

Is there any literature about the complexity of the integer knapsack problem with bounded weights? To make it clear, I want an optimal solution to the following problem: $\max \sum_{i=1}^k c_i \cdot ...
4
votes
0answers
42 views

Adversarial bin packing

An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$). The ...