If ordered t1, t2, ...
w(S) looks like 1/n[w1 t1 + w2(t1+t2) + w3(t1+t2+t3) + . . . + wn(t1+t2+ . . . tn)]
It can be observed that to minimize this, it would be wise to have the smallest t's as the lowest subscripts (because the higher subscript, the more terms in the "t" factor). Also, since you multiply by w, you want the largest w first since it is then multiplied by the fewest things.
Thus a reasonable greedy strategy would be to order ti/wi in nondecreasing (i.e., increasing) order (smallest t's with largest w's make the smallest ratio)
Hence for all i we want an ordering such that ti/wi < ti+1/wi+1
Proof that this causes a minimization of the mean finish time
Let Sgr be the permutation using the greedy strategy
S = (i1, i2, . . . , in) such that
ti1/wi1 < ti2/wi2 < ... < tin/win
Let Sop be a permutation that optimizes the function. Prove that Sop must look like Sgr
Proof by Induction (and some contradiction in Sop):
If our method is correct then if t1/w1 < t2/w2, w(S) is minimized when S=(i1, i2)
PF/ for n = 2
t1/w1 < t2/w2
Helpful hint: assume you know how to make change for c < i, now make change for i.
The hint suggests to use dynamic programming (principle of optimality - that you know the previous solution(s)). In this algorithm, I will start from the bottom (f(1)) and progress forward. We need to do this anyway since the problem says to construct the table for f(i) for i = 1,2,3,...,n. Thus when we calculate f(i) we already know f(i-1), f(i-2), ... , f(0).
Using this strategy, I look at the i'th term, considering the fact that I may need one higher aj to find f(i) than was needed for f(i-1). However, the next aj may be too many coins for the amount, so I need a minimum.
Note - question at each stage is, "am I using this aj coin or not?"
We will build the array f (the solution)and will use the array A for the coin values. In addition, this code will use an array g which will hold the values of the different temporary calculations for f (depending on which new aj coin is added). This is used to be able to then determine the minimum over the (f(i-aj) + 1) values. Specifically, it is the way to make change for the current i considering past knowledge and an addition of each possible coin. This array is not needed (two variables can be used instead); but it is there to correlate with the specific use of each coin.
Algorithm Change (A[1..m], n) // A is array of available coins, n is amount to change //
Worst case time complexity
hence O(m*n)
There are ways to improve this algorithm. For example, we do not have to have a loop look at all m coins since if i < A(j) then there is not need to look at the higher coins. Does this change the worse case time? Consider avarage time. Is this so easy to do in this problem?
For some good tests to your algorithm, try A={1,2,3,10} with say values 1 to 5
Here is the test with the above algorithm:
f(1) = 1 etc etc etc
and also A={1,25,48} with value 50
The above algorithm for 50 will have
Hence f(50) = 2 (or two coins)
Here is another (recursive) solution. Let's look at it for consideration and time complexity
t1w2 < t2w1
t1w2 + (t1w1 + t2w2) < t2w1 + (t1w1 + t2w2)
t1w1 + (t1 + t2)w2 < t2w2 + (t1 + t2)w1
permutation S=(i1,i2) minimized permutation S=(i2,i1)
Done for n=2
Coin Changing
Array A is distinct coin types; f(i) is the number of minimum coins to make change for i.
{
f(0) = 0 // no money so no change
f(1) = 1 // a1 = 1, so f(1) = 1 coin; f(i) is minimum coins for each i
for i = 2 to n do // the rest of the f(i)'s
g(0) = n+1 // or infinity: g(j) holds potentials - n+1 is max; actually max1<i<n{f(i)} = n
for j = 1 to m do // consider coins from A(j)
if i > A(j) then // only consider coins of lesser or equal value to i
{
g(j) = f(i-A(j)) +1
if g(j) < g(j-1) then f(i) = g(j) // f(i) = minover all j such that i>A(j){f(i - A(j)) +1}
}
next j }
next i }
}
1st for loop (2 to n) is n-1 times
2nd for loop (1 to m) is m times
f(2) will consider g(1) = f(2-1) + 1= 1+1 = 2 and f(2-2) + 1= 0 + 1 = 1 HENCE 1
f(3) will consider g(1) = f(3-1) + 1= 1+1 = 2 and f(3-2) + 1= 1 + 1 = 2 and f(3-3) + 1 = 0 + 1 = 1 HENCE 1
f(4) will consider g(1) = f(4-1) + 1= 1+1 = 2 and f(4-2) + 1= 1 + 1 = 2 and f(4-3) + 1 = 1 + 1 = 2 HENCE 2
g(1) = f(50 - 1) + 1 = f(49) + 1 = 2 + 1 = 3
g(2) = f(50 - 25) + 1 = f(25) + 1 = 1 + 1 = 2
g(3) = f(50 - 48) + 1 = f(2) + 1 = 2 + 1 = 3