Tag: Knapsack

Multi-dimensional Knapsack with Minimum Value constraints for Dimensions

In MDK, we have a vector $ W = \{W_1, W_2, …, W_d\}$ where each element corresponds to the maximum weight for the respective dimension in the knapsack.

I want to add a conditional constraint: $ V = {V_1, V_2, …, V_d}$ , where each $ i$ -th dimension in the knapsack must have a value sum greater than threshold $ V_i$ . I am not so much concerned with the total value sum.

I would like to show this problem is NP-hard. My intuition is that the additional constraint makes this problem harder than MKD and therefore is NP-hard. But clearly this doesn’t constitute a formal proof.

0/1 Knapsack algorithm with memoization slow (C#) [closed]

I’m solving a knapsack problem here. It works, but gives time limit exceeds on a certain test case.

Problem statement

There are N items, numbered 1,2,…,N. For each i (1≤i≤N), Item i has a weight of wi and a value of vi

Taro has decided to choose some of the N items and carry them home in a knapsack. The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W

Find the maximum possible sum of the values of items that Taro takes home.

The input is in the following form:

N W w1 v1 w2 v2 : wN vN

N: Number of items.

W: Max weight I can have.

wi: ith weight.

vi: ith value.

Here is my solution to it:

using System; using System.Collections.Generic;  public static class Solution {   // Both s_weights and s_values will have the same length.   private static int[] s_weights; // array holding the weights of the items.   private static int[] s_values; // array holding the values of the items.   private static Dictionary<(int, int), long> s_memo; // memoization dictionary.    // NOTE: I cannot use an array instead of a dictionary here, cause it   // will be a very large 2d array and will give OutOfMemoryException.    public static void Main()   {     // Read the first line, which contains number of items and max weight.     string[] nw = Console.ReadLine().Split(' ');     // Parse n.     int n = int.Parse(nw[0]);     // Parse the max weight.     int maxWeight = int.Parse(nw[1]);      s_weights = new int[n];     s_values = new int[n];     // arbitrary high capacity dictionary to avoid resizing which is O(n).     s_memo = new Dictionary<(int, int), long>(10000000);      // Read each line from the input.     for (int i = 0; i < n; i++)     {       string[] wv = Console.ReadLine().Split(' ');       s_weights[i] = int.Parse(wv[0]);       s_values[i] = int.Parse(wv[1]);     }     // Start the recursion with the maximum weight and all the items.     Console.WriteLine(Solve(maxWeight, n));   }    private static long Solve(int weightLeft, int numberOfItemsToConsider)   {     // simple base case.     if (weightLeft == 0 || numberOfItemsToConsider == 0) return 0;      // If already calculated, get it from the dictionary.     if (s_memo.TryGetValue((weightLeft, numberOfItemsToConsider), out var cachedValue))     {       return cachedValue;     }      // Recursive call calculating the solution if we don't take the current item.     long dontTakeCurrent = Solve(weightLeft, numberOfItemsToConsider - 1);     long result;      // Can we take the current item? If yes, calculate the solution.     if (weightLeft >= s_weights[numberOfItemsToConsider - 1])     {       long takeCurrent = s_values[numberOfItemsToConsider - 1] + Solve(weightLeft - s_weights[numberOfItemsToConsider - 1], numberOfItemsToConsider - 1);       // Maximize the value between the two cases, taking or not taking the item.       result = Math.Max(takeCurrent, dontTakeCurrent);       // Add the result to the memo dictionary.       s_memo.Add((weightLeft, numberOfItemsToConsider), result);       return result;     }     // Here, we don't have another choice other than not taking the item.     result = dontTakeCurrent;     s_memo.Add((weightLeft, numberOfItemsToConsider), result);     return result;   }                           }

Note: I’ve already asked the question in codereview but no answer until now, so I thought cs could be a better place to ask about it.

Why Knapsack problem is not a LP problem?

We know that LP can solve optimization problems that gas linear constraints and linear objective functions. Knapsack problem can be formulated into a linear objective function (because it is just a summation of Pi*Xi) and linear constraints (because it is just a summation of the items weights which should be <= the knapsack weight), so why we can’t consider it an LP problem?

Is the knapsack problem NP-hard when $v_i=i$?

The knapsack problem is NP-hard and can be formulated as: $ $ \begin{align}&\text{maximize } \sum_{i=1}^n v_i x_i,\tag{P1}\& \text{subject to } \sum_{i=1}^n w_i x_i \leq W,\&\text{and } x_i \in \{0,1\}.\end{align}$ $

What if $ v_i=i$ ? Is it still NP-hard?

$ $ \begin{align}&\text{maximize } \sum_{i=1}^n ix_i,\tag{P2}\& \text{subject to } \sum_{i=1}^n w_i x_i \leq W,\&\text{and } x_i \in \{0,1\}.\end{align}$ $

I am trying to reduce (P1) to (P2). Given an instance of (P1), I create the same number of items, same weights. Now, I have to relate the solutions to (P1) and (P2).

Maximum-density multiple-choice knapsack problem

I am looking for work done on solving a problem which is very similar to a combination of two variations of the knapsack problem: maximum-density knapsack problem and multiple-choice knapsack problem.

The problem is: a family of $ t$ sets where all the sets are of the same size $ k$ and the $ j$ -th value in each set $ S_i$ represents some profit, $ P_i(j)$ . Additionaly, the $ j$ -th value of each set is associated with the same cost $ C(j)$ . Both the Profit and the Cost are monotonic: $ C(j_1) \leq C(j_2)$ iff $ {j_1} \leq {j_2}$ and $ P_i(j_1) \leq P_i(j_2)$ iff $ {j_1} \leq {j_2}$ .

Example for some set and costs: $ $ S_1=\{P_1(0)=0,P_1(1)=3,P_1(2)=5,…\}$ $ $ $ C=\{C(0)=0, C(1)=4, C(2)=8,…\}$ $

The problem is to find the chosen elements from each set $ j_i$ such that it solves: $ $ max\{\frac{\sum_{i=1}^{t}P_{i}(j_i)}{\sum_{i=1}^{t}C(j_i)}\} \text{ s.t } {\sum_{i=1}^{t}P_{i}(j_i)} \geq r*{\sum_{i=1}^{t}P_{i}(k)}, 0 \leq r \leq 1$ $
where $ r$ is some given parameter.

Intuitively, you need to maximize the ratio between the profit and the cost while having at least some portion of the profit.

As I said this problem can probably be reduced to a combination of maximum-density knapsack problem and multiple-choice knapsack problem, so any information on that (and not specifically on the problem I stated) can be helpful as well.

Knapsack Problem with exact required item number constraint

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 w), but you must add exactly L item(s) to the knapsack (and obviously need to optimize the total value of the knapsack).

Every way I’ve thought of implementing this so far (dynamic programming, brute force) has resulted in either failure, or lifetime-of-universe level computation times. Any help or ideas are appreciated.

Queries on unbounded knapsack

Given $ n$ types of items with integer cost $ c_{i}$ (there is an unlimited number of items of each type), such that $ c_{i} \leq c$ for all $ i = 1, 2, \dots, n$ , answer (a lot of) queries of form “is there some set of items of total weight $ w$ ?” in time $ O(1)$ with some kind of precalculation in time $ O(n c \log c)$ .

I’ve got a hint – for every $ i = 0, 1, 2, \dots, c – 1$ find minimal $ x$ such that there is a set of items with total weight $ x$ and $ x \equiv i \quad (\bmod c)$ . How to calculate all $ x$ ‘s and how to use them to answer the queries?

This problem is somehow related to graphs and shortest paths, but I don’t understand the connection between actual knapsack-like thing and graphs (maybe there is some graph with paths of desired weight?).

Source: problem 76 on neerc.ifmo.ru wiki.

0/1 Knapsack in bottom up approach

I’ve tried the Recursive, Memoization and DP-Top-Down approach of Knapsack problem. But not able to restructure the code for DP-Bottom-Up approach. Below is my code, its only working for fewer inputs.

def knapsackBFBottomUp(W, val, wt):     n = len(val)     dp = [[0 for i in range(W+1)] for i in range(n+1)]      for i in range(n-1, -1, -1):         for j in range(W-1, -1, -1):             if j > wt[i]:                 ans = dp[i+1][j]             else:                 ans1 = val[i] + dp[i+1][j+wt[i]]                 ans2 = dp[i+1][j]                 ans = max(ans1, ans2)             dp[i][j] = ans     return dp[0][0]   n = int(input()) W = int(input()) val = list(int(i) for i in input().strip().split(' ')) wt = list(int(i) for i in input().strip().split(' ')) print(knapsackBFBottomUp(W, val, wt))  Input Which I've used. 3 2 20 30 40 1 1 1  Returns Answer as 70

Can any one please assist me what I’m missing here? I’ll be very thankful to you.

Knapsack Problem: Understanding the working

I am reading about KnapSack problem from the following link1:

Example of a KnapSack Problem

+----------+---+---+---+---+ |   Item   | 1 | 2 | 3 | 4 | +----------+---+---+---+---+ |  Weight  | 1 | 3 | 4 | 5 | +----------+---+---+---+---+ |   Value  | 1 | 4 | 5 | 7 | +----------+---+---+---+---+

n represents the number of items and w represents weight units. There should be n+1 rows and w+1 columns as discussed in the link:

Another Example from another site

In the example we have w = 7 and n= 4, therefore there should be 5 rows and 8 columns. There are 8 columns but only 4 rows.

Q. I can’t understand why they have 4 rows?

Then they started filling the first column: Table[0][0], Table1[0], Table2[0], Table[3][0]. This will all be zeros, this is because capacity is zero in all the above cases.

But for first row, I am confused:

Table[0][0]: capacity is 0, so its 0 (OK)   Table [0][1]: capacity is 1, so its 1 (OK)  Table[0][2]: capacity is 2, but no item with weight 2, so 1 is fine  Table[0][3]: capacity is 3, we have an item of weight 3 so we can write 3, but they wrote 1, I can n’t understand

Some body please guide me.