Dynamic Programming

zero-impact · **Posted:** Mon Feb 23, 2009 10:57 pm

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

Analysis Mode · **Posted:** Mon Feb 23, 2009 11:38 pm

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.

zero-impact · **Posted:** Tue Feb 24, 2009 7:03 am

Hmmm I don't think that is it. Because it works for the first two cases and not the third :s

saltpro15 · **Posted:** Tue Feb 24, 2009 3:12 pm

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

saltpro15 · **Posted:** Tue Feb 24, 2009 3:43 pm

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

A.J · **Posted:** Tue Feb 24, 2009 4:28 pm

it looks nice Wink

looks like it should work

saltpro15 · **Posted:** Tue Feb 24, 2009 5:40 pm

should, yet doesn't... i'm baffled zeroimpact, that should work, maybe c++ is having a crazy day again

saltpro15 · **Posted:** Tue Feb 24, 2009 5:45 pm

btw, -6 karma ????!!!?! paul, how do I just know that at least 5 of these are from you

A.J · **Posted:** Tue Feb 24, 2009 5:53 pm

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)

saltpro15 · **Posted:** Tue Feb 24, 2009 6:00 pm

umm A.J, i don't see a difference between those blocks...

zero-impact · **Posted:** Tue Feb 24, 2009 6:01 pm

Did you test that A.J? Because even with that change it still only gets the first two cases for me.

saltpro15 · **Posted:** Tue Feb 24, 2009 6:03 pm

can't edit replied to post... irritating Shocked

well no matter, I found it, and it outputs the same thing

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members