Dynamic Programming

Dynamic Programming

A. First Edition

Is dynamic programming really dynamic? Or in a sense become "static" because you mechanically try to solve in

advance all potential sub-problem which might never be using in your search. Then why don't you PROGRAM

really DYNAMICALLY?

B.The problem

Dynamic programming is regarded as intellectual shallow by our professor because it is only an alternate for

recursion. The idea is only one sentence: in order to avoid repeated calling of the same recursive functions,

try to solve all possible sub-problem in a rather linear method. This is rough idea I got from lecture. However,

dynamic programming has one potential problem: you might brute-force all sub-problems which is possibly useless.

Since your recursion may never need to call such sub-problems. This is the trade off of dynamic programming. You

try to avoid repeat calling same recursion and solve all potential problem once in all and you also waste your

resource to solve those you never need to solve.

Is it all? Maybe not.

In the following "set sum" problem, I try to demo for a little dynamic-programming by "checking the cases you

have calculated BEFORE the recursive call". You avoid the repeat call and you execute all you need in recursive.

In short, you have both advantages of recursion and dynamic-programming.

The problem of "set sum":

Design a dynamic programming algorithm which, given positive

integers a1, a2, . . . an, and b, returns either yes to signify that the equation

sum(aixi) = b

has a solution in zeros and ones or no to signify that the equation has no

such solution. With arithmetic operations on and comparisons of integers

taking time O(1), your algorithm must run in time O(nb).

Present your algorithm in the pseudocode style of Question 1.

One solution:

Answer (0, 0) =yes;

for t = 1 to b do Answer (0, t) =no end

for k = 1 to n

do for t = 0 to b

do if a[k]<= t and Answer (k - 1, t - ak) =yes

then Answer (k, t) =yes;

else Answer (k, t) =Answer (k - 1, t);

end

end

end

return Answer (n, b);

C.The idea of program

It is very straight-forward by recording all the recursive cases you have calculated. Then before

each recursive call, check the records. If you have calculated the case, you return the result

directly. Is that shallow? But quite useful.

The only thing troubles me a lot is how to output the result. I mean how to pick up those numbers

you have chosen. Finally, I used a Boolean array to store the number I picked up before each call.

D.The major functions

E.Further improvement

F.File listing

1. dynamicprogramming.cpp

file name: monotone.cpp

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

const int MaxNumber=100;
const int MaxNumberCount=20;
const int MaxSolutionNumber=1000;


int array[MaxNumberCount];

void initialize();
void printAnswer();
bool findAnswer();

bool check(int index, int solution);

bool in[MaxNumberCount];

bool answers[MaxNumberCount+1][MaxSolutionNumber+1]={false};

//0 means unexplored, 1 mean positive, -1 means negative
int answerArray[MaxNumberCount][MaxSolutionNumber]={0};

bool findAnswers(int index, int solution);

void displayArray();

int number;
int dynaCounter=0;
int recurCounter=0;

int main()
{	
	srand(time(0));
	initialize();
	displayArray();
	printf("please input your number for sum(between 1 and 1000):");
	scanf("%d", &number);
	if (findAnswer())
	{
		printf("true\n");
	}
	else
	{
		printf("false\n");
	}
	printf("dynamic programming running counter:%d\n", dynaCounter);

	if (findAnswers(MaxNumberCount-1, number))
	{
		printf("true\n");
		printAnswer();
	}
	else
	{
		printf("false\n");
	}
	printf("recursive programming running counter:%d\n", recurCounter);

	return 0;
}

void printAnswer()
{
	int result=0;
	bool first=true;
	for (int i=0; i<MaxNumberCount; i++)
	{
		if (in[i])
		{			
			
			if (!first)
			{
				printf("+");
			}
			
			if (first)
			{					
				first=false;
			}
			printf("%d ", array[i]);
			result+=array[i];
		}
	}
	if (result==number)
	{
		printf("=%d\n", number);
	}
	else
	{
		printf("wrong!\n");
	}
}

bool findAnswers(int index, int solution)
{
	bool result;
	recurCounter++;
	//printf("index=%d, solution=%d\n", index, solution);

	
	
	//here is dynamic programming, because you check previous record
	//before you make recursive call, as long as checking previous record is
	//fast and resource-efficient, it is worthwhile. Since you dynamically change
	//the execution sequence.
	if (answerArray[index][solution]!=0)
	{
		recurCounter++;
		return answerArray[index][solution]==1;
	}
	else
	{
		//always true if you give all 0 coefficients for all numbers
		recurCounter++;
		if (solution==array[index])
		{
			recurCounter++;
			answerArray[index][solution]=1;

			in[index]=true;
			//printf("result is array[%d]:%d\n", index, array[index]);
			
			return true;
		}
		if (index==0)
		{
			recurCounter++;
			answerArray[index][solution]=-1;
			return false;
		}
		recurCounter++;
		if (solution<array[index])
		{
			recurCounter++;
			answerArray[index][solution]=-1;
			return findAnswers(index-1, solution);
		}
		else
		{
			result=findAnswers(index-1, solution-array[index]);
			if (result)
			{
				in[index]=true;
				return true;
			}
			result=findAnswers(index-1, solution);
			if (result)
			{
				in[index]=false;
				return true;
			}
			//return findAnswers(index-1, solution-array[index])||findAnswers(index-1, solution);
			return false;
		}

		//recursive, arraySize-1 is the index of last entry in array
		/*
		result=findAnswers(index-1, solution);
		if (result)
		{
			printf("result is array[%d]:%d\n", index-1, array[index-1]);
			return true;
		}
		result=findAnswers(index-1, solution-array[index]);
		if (result)
		{
			printf("result is array[%d]:%d\n", index-1, array[index-1]);
			return true;
		}
		return false;
		*/
		//return findAnswers(index-1, solution)||findAnswers(index-1, solution-array[index]);
	}
}



void displayArray()
{
	for (int i=0; i<MaxNumberCount; i++)
	{
		printf("array[%d]:%d\n", i, array[i]);
	}
}

/*
bool check(int index, int solution)
{
	if (index==0||array[index]>solution)
	{
		return false;
	}
	if (answers[index-1][solution-array[index]])
	{
		return true;
	}
	return false;
}
*/

void initialize()
{
	for (int i=0; i<MaxNumberCount; i++)
	{		
		array[i]=rand()%MaxNumber+1;//at least 1, at most 100
		for (int j=0; j<MaxSolutionNumber; j++)
		{
			answerArray[i][j]=0;
		}
	}
}

bool findAnswer()
{
	dynaCounter++;
	answers[0][0]=true;
	for (int i=1; i<=number; i++)
	{
		dynaCounter++;
		answers[0][i]=false;
	}
	for (int index=1; index<=MaxNumberCount; index++)
	{
		for (int solution=0; solution<=number; solution++)
		{
			//this is very dangerous!!!it only work if compiler use a shortcut for "and"
			if (array[index-1]<=solution)
			{
				if (answers[index-1][solution-array[index-1]])
				{
					answers[index][solution]=true;
				}
				else
				{
					answers[index][solution]=answers[index-1][solution];
				}
			}
			else
			{
				answers[index][solution]=answers[index-1][solution];
			}
			dynaCounter++;
		}
	}
	return answers[MaxNumberCount][number];
}

How to run?

The running result is a kind of impressive. As you see, by mechanically calculating all sub-problems you have to

waste more than 10 times of resources than "dynamic-programming". Of course here I measure in the sense of number

of comparison and updating of entries which record your result.

1. This rather small number 209 saves roughly 10 times of time.

array[0]:7
array[1]:58
array[2]:95
array[3]:72
array[4]:24
array[5]:34
array[6]:98
array[7]:9
array[8]:86
array[9]:59
array[10]:48
array[11]:89
array[12]:43
array[13]:99
array[14]:48
array[15]:13
array[16]:27
array[17]:20
array[18]:13
array[19]:73
please input your number for sum(between 1 and 1000):209
true
dynamic programming running counter:4410
true
24 +9 +43 +27 +20 +13 +73 =209
recursive programming running counter:471
Press any key to continue

1. This rather big number 500 saves roughly 20 times of time.

array[0]:22
array[1]:36
array[2]:49
array[3]:88
array[4]:86
array[5]:98
array[6]:30
array[7]:58
array[8]:68
array[9]:52
array[10]:71
array[11]:31
array[12]:71
array[13]:65
array[14]:42
array[15]:22
array[16]:53
array[17]:43
array[18]:53
array[19]:37
please input your number for sum(between 1 and 1000):500
true
dynamic programming running counter:10521
true
86 +68 +31 +65 +42 +22 +53 +43 +53 +37 =500
recursive programming running counter:822
Press any key to continue

3. This rather extreme case is most astonishing! Because you don't have to establish a case that

is obviously impossible.

array[0]:23
array[1]:57
array[2]:82
array[3]:87
array[4]:58
array[5]:22
array[6]:12
array[7]:17
array[8]:7
array[9]:2
array[10]:86
array[11]:96
array[12]:48
array[13]:13
array[14]:71
array[15]:47
array[16]:43
array[17]:69
array[18]:69
array[19]:37
please input your number for sum(between 1 and 1000):1000
false
dynamic programming running counter:21021
false
recursive programming running counter:2
Press any key to continue