Tag Info

Accepted

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

When we say polynomial or exponential, we mean polynomial or exponential in some variable. $nW$ is polynomial in $n$ and $W$. However, we usually consider the running time of an algorithm as a ...
Accepted

• 17.3k

Find non-overlapping scheduled jobs with maximum cost

One could implement this in O(nlogn) Steps: Sort the intervals based on end time define p(i) for each interval, giving the biggest end point which is smaller than the start point of i-th interval. ...
Accepted

• 80.2k
Accepted

Knapsack Problem with exact required item number constraint

You can transform this problem into an instance of Knapsack. Let $n$ be the number of items, $V$ be the maximum value of an item and suppose that each item weighs at most $W$ (otherwise it can be ...
• 23.4k

Detecting conservation, loss, or gain in a crafting game with items and recipes

Your problem is equivalent to asking whether there is some linear combination of row vectors from your $\mathbb R^{m\times n}$ matrix that has all coefficients positive and sums to a vector in which (...
• 5,154
Accepted

Dynamic Programming - Thief Variation Probem

For $i=1,\dots,N$, and $r \in \{S,R,B\}$ define $OPT[i,r]$ as the maximum profit that can be obtained by robbing a suitable subset of the first $i$ houses with the following constraints: If $x=S$ (...
• 23.4k

0/1 knapsack problem: Greedy Algorithm Counterexample

Consider this counterexample. Suppose the knapsack has a capacity 4. And suppose there are three items: Item A with weight 3 and value 5 Item B with weight 2 and value 3 Item C with weight 2 and ...
• 3,976
Accepted

Optimizing NFL draft picks

Yes, this can be solved using a dynamic programming algorithm very similar to the standard dynamic programming algorithm for the knapsack problem. Basically, order the positions from 1 to 9. You're ...
• 141k