# 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.

223 questions
Filter by
Sorted by
Tagged with
79 views

### Proving that a problem is not FPT using reduction

In the Inclusive Vertex Cover problem, For a given graph $G=(V,E)$, each vertex $u\in V(G)$ has weight $u_{w} \in \mathbb{N}$ and value $u_{v}\in \mathbb{N}$. The value and weight of a set cover $S$ ...
19 views

### How do you prove that a solution to the 0-1 knapsack problem is optimal?

Given a boolean vector b representing a solution to the knapsack problem with n elements k capacity and where each element has integer weight and value. Proving that the solution is a solution is ...
46 views

### FPT algorithm for Knapsack

I tried to search whether Knapsack (the decision version) has a FPT algorithm, but didn't find anything on the topic. Can someone help with a reference?
23 views

### Path that stays within a convex polyhedron

Let $\mathcal{P},\mathcal{Q}$ denote two convex polyhedra in $\mathbb{R}^d$, which can be represented by a set of linear inequalities. Let $A \subset \mathbb{R}^d$ be a finite set of vectors. The ...
79 views

### Algorithm for Variant of 0-1 Knapsack Problem

Variant of 0-1 Knapsack Problem is when you can choose exactly $k$ items from $n$ items, and $k$ is positive integer parameter that came in the input. Is there an algorithm with running time ...
50 views

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 ...
66 views

### Knapsack on two kinds of objects, where you cannot choose type 2 objects on their own

I had an online round at a company where I was asked this question. There are $N$ items, and you have to choose some items from them such that the total weight does not exceed $W$. Each item has three ...
39 views

### Optimal Selection of Non-Overlapping Jobs

I'm trying to find what the family of problem is - as well as an approach - for the following: I have a set of tasks T = [t1, ..., tn] to do, each of which has a corresponding reward ri. Each task ...
190 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 ...
75 views

### 0/1 Knapsack problem with minimal cost

so i have this problem where: I have to accomplish a challenge A with n quests. Each quest gives me: p points and needs t time to be done. The object is to complete the challenge A that needs M ...
16k 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 ...
50 views

### How to check if an algorithm's running time is linear/polynomial in its input size? Multiple variables

I am reading a proof that the Subset Sum decision problem is NP-complete. I know that the time complexity is always calculated based on the number of bits of the input in binary, hence the $\log{W}$. ...
29 views

### Transforming a multidimensional 0-1 knapsack problem to a maximum weighted clique problem

Just out of theoretical curiosity, is there a way to transform a 0-1 multimensional knapsack problem to a maximum clique problem? Or maybe even easier, to a maximum weighted clique problem (the ...
122 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 ...
475 views

### How to prove that the subset sum problem is polynomially reducible to the knapsack problem

I want to prove that the subset sum problem is polynomially reducible to the Knapsack problem. Overall I want to show that Knapsack is NP-complete. There are two parts to showing knapsack is NP-...
33 views

### Combinatorial optimization algorithm with constraints and objective function

I'm looking for an algorithm that will let me optimally select items from a set. These items have properties which are involved in defining constraints as well as the objective function. .e.g Say each ...
51 views

### Get $n^{\mathrm{th}}$ element of sorted subset sums

I have a sorted multiset (size < 100, real valued) and want to determine the $n^{\mathrm{th}}$ largest of all possible subset sums (including multiplicity in the sums). Attempt at solving : I have ...
67 views

### 0/1 Knapsack problem. How does the total weight does not exceed the limit?

I am trying to wrap my head around the knapsack problem algorithm. I understood the most of it except one tiny thing. On the left is the [val,weight] and on the ...
9 views

### Creating neighbours of solutions to binary knapsack instances

I am currently trying to implement a Tabu Search algorithm for the binary knapsack problem. Part of my goal is to have a variety of different configurations of attributes used and stopping conditions. ...
595 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)...
20 views

### Optimal way to pack items with multidimensional weight such that the number of items is minimized?

I am given a set of items S = {a1,a2,a3,...,an}. Each item has a corresponding M dimensional bit vector indicating the properties of that item. For example, if item x has corresponding vector: {0, 1, ...
15 views

108 views

### Maximum-density multiple-choice knapsack problem

I am looking for work done on solving a problem (specifically I'm looking for an approximation algorithm) which is very similar to a combination of two variations of the knapsack problem: maximum-...
4k 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 ...
How would we solve the knapsack problem if we now have to fix the number of items in the knapsack by a constant $L$? This is the same problem (max weight of $W$, every item have a value $v$ and weight ...
Given two sets of $N$ integers, weights and reps, that store info about some dumbbells, find out the maximum profit by taking at most $M$ dumbbells. Each dumbbell can be taken at most once. The ...