Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Yet another problem with DP
Index -> Contests
Goto page 1, 2  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
MysticVegeta




PostPosted: Fri Apr 21, 2006 9:15 am   Post subject: Yet another problem with DP

Hey guys, I am working on this problem, where S = sum. The elements of array "arr" tell us the value of each element in integers. And I have to find the minimum # of elements needed from the array "arr" to make the sum S, I dont know where my DP is wrong. Please help me out, the answer is supposed to be 21. It works with some of the other cases but not all.
Java Solution:

code:
import java.io.*;
import java.util.*;
public class Problem
{
    public static void main (String [] Args) throws IOException
    {
                        int arrayLength = 21;
               
                        int S = 123;
                       
                        int [] arr = {7,7,7,7,8,8,8,2,2,2,2,2,2,2,2,2,5,12,12,12,12};
                       
                        Arrays.sort(arr);
                       
                        int [] Min = new int [S+1];
                       
                        Arrays.fill(Min,1000);

                        Min[0] = 0;
                       
                        for (int k = 1; k <= S; k++) {
                                for (int j = 0; j < arrayLength; j++) {
                                        if (arr[j]<=k && Min[k-arr[j]]+1<Min[k]){
                                                Min[k]=Min[k-arr[j]]+1;
                                        }
                                }
                        }
                       
                        System.out.println(Min[S]);
    }
}
Sponsor
Sponsor
Sponsor
sponsor
NikG




PostPosted: Fri Apr 21, 2006 10:22 am   Post subject: (No subject)

I was having a little trouble figuring out what your for loops did (since I have completely forgotten java) so I gave up.

I thought of a solution to this problem though:
-Sort the array from highest to lowest (you did already, right?)
-Keep adding the numbers from the biggest down until you reach a value just smaller than S (obviously if you hit S, you've got your solution). Keep track of the difference from S and your total value so far.
-Once that's done, look for a number/combination of #s in the remaining elements that equal S-difference
-If not found, back up your total value so that it picks up one less element and repeat the above step.

The way I figure it, that should always work
MysticVegeta




PostPosted: Fri Apr 21, 2006 11:17 am   Post subject: (No subject)

That is wayy too much work than the DP solution, besides what if some numbers in the middle of the array are not used? You would need a useless recursion to have all the possibilities and check them. DP is way more efficient since it finds the minimum # of values needed for sums from 1 to S, and uses them to find the minimum # of values needed for the next one.
zylum




PostPosted: Fri Apr 21, 2006 1:07 pm   Post subject: (No subject)

constraints?
md




PostPosted: Fri Apr 21, 2006 3:22 pm   Post subject: (No subject)

NikG's solution is pretty good... it can be improved to take out all recursion though.

Psudo code:
code:

Sort from highest to lowest
A = 0
count = 0
for i = 1 to max do
    if( A + arr[i] <=S)
        A += arr[i]
        count++
    if( A == S)
        return count


Methinks this'll work... though I haven't tested it.
zylum




PostPosted: Fri Apr 21, 2006 4:22 pm   Post subject: (No subject)

greedy wont work in this case...

for example 10 6 5 5 5 5 1 1 1 1 wont work... yours will use 10 6 1 1 1 1 instead of 5 5 5 5
md




PostPosted: Fri Apr 21, 2006 5:51 pm   Post subject: (No subject)

Hmmm... good point... perhaps I should think about this some more
zylum




PostPosted: Fri Apr 21, 2006 10:11 pm   Post subject: (No subject)

here is your dp solution...

code:
const S := 123
const C := 21

var coins : array 1 .. C of int := init (7, 7, 7, 7, 8, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 12, 12, 12, 12)
var dp : array 0 .. S, 0 .. C of int
for i : 0 .. C
    dp (0, i) := 0
end for

for i : 1 .. S
    for j : 1 .. C
        dp (i, j) := 0
    end for
    dp (i, 0) := 1000000
    for j : 1 .. C
        if i - coins (j) >= 0 & dp (i, 0) > dp (i - coins (j), 0) + 1 & dp (i - coins (j), j) = 0 then
            dp (i, 0) := dp (i - coins (j), 0) + 1
            for k : 1 .. C
                dp (i, k) := dp (i - coins (j), k)
            end for
            dp (i, j) := 1
        end if
    end for
end for

put dp (S, 0)
for i : 1 .. C
    if dp (S, i) = 1 then
        put coins (i), " " ..
    end if
end for
Sponsor
Sponsor
Sponsor
sponsor
MysticVegeta




PostPosted: Sat Apr 22, 2006 9:26 am   Post subject: (No subject)

mike, but remember dimitru from tc? he coded the same problem for the novice level of tut as mine, I implemented the exact same algo, whats wrong then? :S
zylum




PostPosted: Sat Apr 22, 2006 10:36 am   Post subject: (No subject)

no, the coin problem can use an unlimited number of the same coin. here you are restricted to one of each.
MysticVegeta




PostPosted: Sat Apr 22, 2006 6:24 pm   Post subject: (No subject)

I am sure there must be another way to do this cause I dont know what the hell you did in that solution lol beyond my knowledge Laughing
zylum




PostPosted: Sat Apr 22, 2006 9:55 pm   Post subject: (No subject)

since you can only use one of each integer, you have to keep track of which you used from state to state. its just an extension to the coin problem.

you know how in the original coin problem you went from state to state (0 .. S) but you dont have to keep track of which coins you used because you can use an unlimited amount. to over come this i used a 2d array from 1..S, 1..C which keeps track of the state and which coins were used. dp(i, 0) stores the amount of coins i used where as dp(i, 1..C) keeps track of which coin was used. so in the dp solution you need one extra case, you have to check if the previous state uses the coin you want to add to the current state. then you copy the coins you used from the previous state to the current state plus the one you added to the current state..

hope that explains it.
MysticVegeta




PostPosted: Sun Apr 23, 2006 10:27 am   Post subject: (No subject)

Thanks for the explanation, Smile I get it now. but cant you use like a boolean array and sort of implement it in dimitrus solution to keep track of used coins?
zylum




PostPosted: Sun Apr 23, 2006 4:17 pm   Post subject: (No subject)

you can but then youd need 2 arrays, this way i kept it it 1. in java though youd probably want to use 2 arrays, one 2d boolean and one regular one as in the coin problem.
andytyk




PostPosted: Sun Apr 23, 2006 5:45 pm   Post subject: (No subject)

I don't think you need to keep track of what you used...

I just modified MysticVegeta's code...

code:

import java.util.*;

public class Problem
{
    public static void main (String [] Args)
    {
        int S = 115;

        int [] arr = {7, 7, 7, 7, 8, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 12, 12, 12, 12};

        int [] Min = new int [S + 1];

        Arrays.fill (Min, Integer.MAX_VALUE);

        Min [0] = 0;

        for (int i = 0 ; i < arr.length ; i++)
            for (int k = Min.length - 1 ; k >= arr [i] ; k--)
                if (Min [k - arr [i]] != Integer.MAX_VALUE)
                    Min [k] = Math.min (Min [k], Min [k - arr [i]] + 1);

        System.out.println (Min [S]);
    }
}
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 2  [ 20 Posts ]
Goto page 1, 2  Next
Jump to:   


Style:  
Search: