Computer Science Canada

Dynamic Programming
Author:  zero-impact [ Mon Feb 23, 2009 10:57 pm ]
Post subject:  Dynamic Programming
I have been working on this question for a while now and can't seem to figure out what is happening.
My situation is that out of the 3 test cases only the first two will produce a correct answer. The strange part is, is that I have been using a friends Turing solution to learn and make a c++ solution of my own (Thank you saltpro15).
My c++ solution seems to be identical (even more so after a change to be exactly the same) to the Turing version yet it still only gets 2/3 and the Turing version 3/3.

Here is the code.

c++:

#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

struct Block
{
        int h;
        int n;
};

int main()
{
        ifstream fin ("dp.txt");
        for (int k = 0; k < 3; k++)
        {
                int height, nBlocks;
                fin >> nBlocks;
                Block blocks [nBlocks];

                for (int i = 0; i < nBlocks; i++) //Reading in
                {       
                        fin >>blocks[i].h>>blocks[i].n;
                }
                fin >> height;
               
                int dp [height];
                memset (dp,0x7f,sizeof(dp)); //Set array to  2139062143
                dp [0] = 0;
               
                for (int i = 0; i <= nBlocks; i++) //Dp
                {
                        for (int j = 0; j < blocks [i].n; j++)
                        {
                                for (int k = height; k >= blocks [i].n; k--) //for (int k = blocks [i]; k < height; k++)
                                {
                                        dp[k] = min(dp [k],dp [k - blocks [i].h] + 1);
                                }
                        }
                }
               
                /*for (int i = 0; i <= height; i++)
                        cout << dp [i] <<" ";
                */
                //cout << endl;
                cout << dp [height]<<" ";
                //cout <<endl<<endl;
        }
        return 0;
}


Turing:

type blocks :
    record
    num, h : int
    end record
var stream : int
open : stream,"dp.txt",get
for z : 1 .. 3
var n, theight : int
 
get : stream,n
 
var b : array 1 .. n of blocks
 
for i : 1 .. n
    get : stream,b (i).h, b (i).num
end for
 
get :stream ,theight
 
var dp : array 0 .. theight of int
 
for i : 1 .. theight
    dp (i) := 999999 % set the dp array to a huge number initially
end for
 
dp (0) := 0
 
for i : 1 .. n
    for j : 1 .. b (i).num
    for decreasing k : theight .. b (i).h
        dp (k) := min (dp (k), dp (k - b (i).h) + 1)
    end for
    end for
end for
 
put dp (theight)
end for


input file
Author:  Analysis Mode [ Mon Feb 23, 2009 11:38 pm ]
Post subject:  Re: Dynamic Programming
int dp [height]; is your DP array declaration, yet at the bottom, you output dp[height]. I think it shold be dp[height+1] (for both output and declaration) That might be your problem.

Dun worry, I've had the same problesm when translating code from pascal to c++ myself.

your algorithm looks fine.
Author:  zero-impact [ Tue Feb 24, 2009 7:03 am ]
Post subject:  RE:Dynamic Programming
Hmmm I don't think that is it. Because it works for the first two cases and not the third :s
Author:  saltpro15 [ Tue Feb 24, 2009 3:12 pm ]
Post subject:  RE:Dynamic Programming
umm... I was consulting with A.J. as to how to do this problem, and I think I saved his solution over mine, because that is not my code, although it does look a lot like it, I take no credit for that
Author:  saltpro15 [ Tue Feb 24, 2009 3:43 pm ]
Post subject:  Re: Dynamic Programming
This is my version, oops, sorry AJ Embarassed
Turing:

type bloks :

    record

        n_, h : int

    end record



var input, output : int

open : input, "DPIN.txt", get

open : output, "DPOUT.txt", put

for asdf : 1..3

var n, towerh : int

get : input, n, towerh

var t : array 1..n of bloks

var dp : array 1..towerh of int

for i : 1 .. n

    get :input, t (i).h, t (i).n_

end for

   

 for i : 1 .. towerh

        dp (i) := 1000000

    end for



    dp (0) := 0

    for i : 1 .. n

    for j : 1 .. t (i).n_

        for decreasing k : towerh .. t (i).h

            dp (k) := min (dp (k), dp (k - t (i).h) + 1)

        end for

    end for

end for

    put : output, dp (towerh)

end for



put Time.Elapsed/1000
Author:  A.J [ Tue Feb 24, 2009 4:28 pm ]
Post subject:  Re: Dynamic Programming
it looks nice Wink

looks like it should work
Author:  saltpro15 [ Tue Feb 24, 2009 5:40 pm ]
Post subject:  RE:Dynamic Programming
should, yet doesn't... i'm baffled zeroimpact, that should work, maybe c++ is having a crazy day again
Author:  saltpro15 [ Tue Feb 24, 2009 5:45 pm ]
Post subject:  RE:Dynamic Programming
btw, -6 karma ????!!!?! paul, how do I just know that at least 5 of these are from you
Author:  A.J [ Tue Feb 24, 2009 5:53 pm ]
Post subject:  Re: Dynamic Programming
I found your mistake

c++:

                for (int i = 0; i <= nBlocks; i++) //Dp
                {
                        for (int j = 0; j < blocks [i].n; j++)
                        {


should be :

c++:

                for (int i = 0; i < nBlocks; i++) //Dp
                {
                        for (int j = 0; j < blocks [i].n; j++)
                        {


the first loop must go from 0 -> nBlocks - 1 (since blocks[nBlocks] doesn't hold anything)
Author:  saltpro15 [ Tue Feb 24, 2009 6:00 pm ]
Post subject:  RE:Dynamic Programming
umm A.J, i don't see a difference between those blocks...
Author:  zero-impact [ Tue Feb 24, 2009 6:01 pm ]
Post subject:  RE:Dynamic Programming
Did you test that A.J? Because even with that change it still only gets the first two cases for me.
Author:  saltpro15 [ Tue Feb 24, 2009 6:03 pm ]
Post subject:  RE:Dynamic Programming
can't edit replied to post... irritating Shocked well no matter, I found it, and it outputs the same thing

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy