DP and Greedy
BY
Shubhang Walavalkar
Sanjay Bhat
Tarun Joshi
Greedy Algorithms
Given a set of items, each with a weight and a value, determine the maximum amount of
value obtained by putting items in the knapsack (fractions are allowed) such that the
total weight of the items doesn't exceed the maximum limit of the knapsack.
Greedy Strategy : Choose the item with the max value of
profit/weight ratio first. Why max ? because we want
profit to be max and weight to be min.
Proof:
https://courses.cs.duke.edu/spring19/compsci330/lectu
re8scribe.pdf
Few more problems:
1)https://codeforces.com/problemset/problem/1343/C
2) https://cses.fi/problemset/task/1074
3) https://codeforces.com/problemset/problem/1539/C
4) https://codeforces.com/contest/1154/problem/D
1D - DP
Fibonacci
Time complexity:
O(ϕ^n) or O(1.618^n)
ϕ^n is tight upper bound which can be calculated by using mathematically represented linear
recursive function
refer :
1. https://www.geeksforgeeks.org/time-complexity-recursive-fibonacci-program/
2. https://www.quora.com/What-is-the-time-complexity-of-calculating-Fibonacci-numbers-using-recursion
T(n) = T(n-1) + T(n-2) + O(1)
On solving the above recursive equation we get the upper bound of Fibonacci as O(2^n) but
this is not the tight upper bound.
from 2666ms it reduced to 4ms
Recursive VS Recursive DP
TIMED_OUT > 5s
5MS
HW Problems :)
1. https://bit.ly/3JPcoOx
2. https://bit.ly/3q5rlUY
3. https://bit.ly/3F4yl8z (2d dp)
4. CSES DP problem set
Minimizing Coin
Problem statement:
You are given an array of ‘N’ distinct integers and an integer ‘X’ representing the target
sum. You have to tell the minimum number of elements you have to take to reach the
target sum ‘X’.
problem link: https://bit.ly/3HJTeIl
Why a Greedy Solution doesn’t work?
The first approach that comes to our mind is greedy. A greedy solution will
fail in this problem because there is no ‘uniformity’ in data. While selecting a
local better choice we may choose an item that will in the long term give less
value
Example: arr ={ 9,6,5,1} target sum= 11
A Greedy solution will be to take the highest denomination coin first, so we will take an item on
index 0, with a value of 9. Now the remaining target sum will be 2. Therefore we can only
consider coins with a value of 1. We will take 2 coins of value 1 to meet the target. So a greedy
solution gives us the answer 3 {9,1,1}
Now we can clearly see that a non-greedy solution of taking 2 coins valued 6 and 5 will give us
a better option. So we can say that the greedy solution doesn’t work for this problem.
BASE case: Recursive way
if target ==0:
return 0;
Using 1D-DP ,
Memoization
Time Complexity: O(N*T)
Reason: There are N*T states
therefore at max ‘N*T’ new problems
will be solved.
Space Complexity: O(N*T) + O(N)
We are using a recursion stack
space(O(N))
The Fractional and 0/1 Knapsack :
An Intro to 2-D DP
Given the weights and profits of N items, in the form of
{profit, weight} put these items in a knapsack of capacity W
to get the maximum total profit in the knapsack. In
Fractional Knapsack, we can break items for maximizing
the total value of the knapsack.
Max capacity of knapsack = 3
Now what if taking fractional parts of an item was not
allowed ?
More formally, now you can either select an item or not
select an item there’s no in between .
Item No 1 2 3
Profit 5 4 2 Max weight
Weight 10 9 1
= 10
Profit/Weight 0.5 0.44 2
So be pro and do DP bro
Lets define a function f (i,x) :
f(i,x) holds the max value using the first i items if the
knapsack’s max weight is x.
So lets say we have already calculated f(j,k) for all j < i
and k <= x.
Then what would be the value of f(i,x) ?
HINT : We only have two options, either to choose the
ith item or not choose it.
1) Suppose we dont chose the ith element:
Then the answer would be f(i-1,x) since we are now
only bothered about the first i-1 items.
2) Suppose we decided to choose the ith element :
Then the leftover weight of the knapsack is x - weight[i].
Then out of the i-1 elements left, we need the max value
which fits in the knapsack with weight x - weight[i].
Thus here, f(i,x) = value[i] + f(i-1,x-weight[i])
Since we want max of both cases, we say f(i,x) is max
of case 1 and case 2.
Thus the final recurrence is :
f(i,x) = max( f(i-1,x), value[i] + f(i-1, x - weight[i]) )
Note that this involves overlapping subproblems, for
example if f(i+1,y) needs the answer of f(i,x) instead of
again finding the answer of f(i,x) we can just store it in a
2D array as dp[i][x].
This part takes care of the memoization.
Sample code :
