-----------------------------------

zero-impact

Mon Feb 23, 2009 10:57 pm


Dynamic Programming

-----------------------------------

I have been working on 
#include 
#include 
#include 
#include 
#include 

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 


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

Mon Feb 23, 2009 11:38 pm


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.


-----------------------------------

zero-impact

Tue Feb 24, 2009 7:03 am


RE:Dynamic Programming

-----------------------------------

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


-----------------------------------

saltpro15

Tue Feb 24, 2009 3:12 pm


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


-----------------------------------

saltpro15

Tue Feb 24, 2009 3:43 pm


Re: Dynamic Programming

-----------------------------------

This is my version, oops, sorry AJ  :oops:

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

Tue Feb 24, 2009 4:28 pm


Re: Dynamic Programming

-----------------------------------

it looks nice :wink: 

looks like it should work


-----------------------------------

saltpro15

Tue Feb 24, 2009 5:40 pm


RE:Dynamic Programming

-----------------------------------

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


-----------------------------------

saltpro15

Tue Feb 24, 2009 5:45 pm


RE:Dynamic Programming

-----------------------------------

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


-----------------------------------

A.J

Tue Feb 24, 2009 5:53 pm


Re: Dynamic Programming

-----------------------------------

I found your mistake


		for (int i = 0; i  nBlocks - 1 (since blocks[nBlocks] doesn't hold anything)


-----------------------------------

saltpro15

Tue Feb 24, 2009 6:00 pm


RE:Dynamic Programming

-----------------------------------

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


-----------------------------------

zero-impact

Tue Feb 24, 2009 6:01 pm


RE:Dynamic Programming

-----------------------------------

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


-----------------------------------

saltpro15

Tue Feb 24, 2009 6:03 pm


RE:Dynamic Programming

-----------------------------------

can't edit replied to post... irritating :shock: well no matter, I found it, and it outputs the same thing