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

1
vote
2answers
89 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
560 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
60 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
72 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
77 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
38 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
82 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
40 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
48 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
114 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
56 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? ...
1
vote
1answer
72 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
48 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
123 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
26 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
59 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 ...
0
votes
1answer
53 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
443 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
27 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
113 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, ...
0
votes
0answers
30 views

The variance of knapsack minimizing error between maximum load and sum of packing items

The constraint of basic knapsack problem is the sum of packed item should be less than the maximum load. I'm interested in the variance of it where the objective is minimizing the difference between ...
4
votes
1answer
122 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
21 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
43 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
128 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
70 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
78 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
45 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
100 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
29 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
352 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
373 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
2k 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
67 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
219 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
79 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
213 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
91 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
92 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 ...
2
votes
1answer
990 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
770 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
118 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 ...
3
votes
0answers
36 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 ...
3
votes
1answer
2k views

Variant of the knapsack problem

How would you approach the knapsack problem in a dynamic programming situation if you now have to limit the number of item in the knapsack by a constant $p$ ? This is the same problem (max weight of ...
2
votes
1answer
3k views

Confusion related to time complexity of dynamic programming algorithm for knapsack problem

I have this confusion related to the time complexity of the algorithm solving the knapsack problem using dynamic programming I didn't get how the time complexity of the algorithm came out to be ...
6
votes
4answers
3k views

Find non-overlapping scheduled jobs with maximum cost

Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum. Now I'm not sure if a greedy algorithm will do the trick. That is, sort by ...
-5
votes
1answer
231 views

Maximizing profit

Problem: Given 11 numbers {N1,N2,N3,N4,N5,N6,N7,N8,N9,N10,N11} where N1:amount of profit from product A N2:amount of profit from Product B N3:amount of ...
3
votes
0answers
384 views

Dynamic Knapsack Problem - Algorithms and References

I don't know the right name for this problem, or if there is a name, but it is inspired by my initial interpretation of the title of this question (my question is very different, so the link may be ...
0
votes
1answer
748 views

Knapsack problem with multiple constraints

I am unsure if I have even identified the problem correctly, but reading up on knapsack problem seems the closest to what I am trying to solve: A cook has $k$ ingredients of $p$ quantities. Given ...