Pocket Ruler

    A. First Edition

    This is another example of dynamic programming which is the question of assignment of comp465.

    B.The problem

The problem called FOLDING RULER goes as follows. Given

a ruler made of rigid rods connected end-to-end by hinges (much as a carpenter¡¯s

ruler, except that dierent rods may have dierent lengths), can you

fold it to make it fit in your pocket?

Formally, the input is a sequence of positive integers

a1, a2, . . . , an (the

lengths of the

n consecutive rods) and a positive integer b (the depth of

your pocket); each way of folding the ruler can be represented by a sequence

x

1, x2, . . . , xn such that each xi is +1 (meaning that the i-th rod points up) or

-

1 (meaning that the i-th rod points down); the ruler folded in this particular

way will fit in your pocket if and only if there is an integer

s (representing the

position in your pocket where the beginning point of the ruler finds itself)

such that 0 <=

s <= b and

0

<= s + sum(xiai) <=b for all choices of k = 0, 1, . . . , n.

(For example, the ruler whose sequence of rod lengths is 9,7,3,8 will fit into

a pocket of depth 10: consider

s = 1, x1 = +1, x2 = -1, x3 = -1, x4 = +1.)

Design a dynamic programming algorithm for solving this problem and

present it the pseudo code style of Question 1, Homework Assignment 3.

C.The idea of program
¡¡

My experience is that dynamic programming is simply an variation of recursion. Therefore it is always helpful

if you can figure out the recursive version of program first.

The other thing apart from efficiency I don't like about dynamic programming is that it is very difficult to

find the path. In this problem, I cannot find the solution for the question except a Boolean answer.

    D.The major functions

    ¡¡

    E.Further improvement

    ¡¡

    F.File listing

    1. Ruler.cpp

    ¡¡

    file name: LCS.cpp

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

    const int RulerNumber=15;
    const int MaxHeight=100;

    int positions[RulerNumber][MaxHeight];//0: unknown, 1: ok, -1 no;

    int rulers[RulerNumber];
    //Record records[MaxLengthNumber*2];

    int choices[RulerNumber];//either 1 or -1

    void initialize();
    void display();

    void dynaFind();
    void statFind();

    bool findRuler(int step, int current);

    int height;

    int main()
    {
    	initialize();
    	display();
    	printf("input the length you want:");
    	scanf("%d", &height);

    	statFind();
    	dynaFind();
    	return 0;
    }

    void dynaFind()
    {
    	int index;
    	//bool secondTry;
    	for (int step=0; step<RulerNumber; step++)
    	{
    		for (int cur=0; cur<height; cur++)
    		{
    			if (step==0)
    			{
    				if (cur==height-rulers[0])
    				{
    					positions[step][cur]=1;
    				}
    				else
    				{
    					positions[step][cur]=-1;
    				}
    			}
    			else
    			{

    				positions[step][cur]=-1;
    				//not exceeds bound
    				index=cur-rulers[step];
    				if (index>=0)
    				{
    					//last is ok
    					if (positions[step-1][index]==1)
    					{
    						if (step==RulerNumber-1)
    						{
    							printf("\nthere is a solution for dynamic programming.\n");
    							return;
    						}
    						positions[step][cur]=1;
    					}
    				}
    				if (positions[step][cur]==-1)
    				{
    					//not exceeds bound
    					index=cur+rulers[step];
    					if (index<height)
    					{
    						//if last row is ok
    						if (positions[step-1][index]==1)
    						{
    							if (step==RulerNumber-1)
    							{
    								printf("\nthere is a solution for dynamic programming.\n");
    								return;
    							}
    							positions[step][cur]=1;
    						}
    					}
    				}
    			}
    		}
    	}
    }

    void statFind()
    {
    	int current;
    	if (findRuler(0, height))
    	{
    		printf("the choices is \n");
    		current=height;

    		for (int i=0; i<RulerNumber; i++)
    		{
    			//printf("choices[%d]=%d\n", i, choices[i]);
    			printf("step%d: %d and position is: ", i, choices[i]);
    			current+=choices[i]*rulers[i];
    			printf("%d\n", current);
    		}
    	}
    	else
    	{
    		printf("no solution\n");
    	}
    }

    void initialize()
    {
    	for (int i=0; i<RulerNumber; i++)
    	{
    		rulers[i]=10+rand()%50;
    		for (int j=0; j<MaxHeight; j++)
    		{
    			positions[i][j]=0;
    		}
    	}

    }

    void display()
    {
    	for (int i=0; i<RulerNumber; i++)
    	{
    		printf("rulers[%d]=%d\n", i, rulers[i]);
    	}
    }

    bool findRuler(int step, int current)
    {
    	if (current>height||current<0)
    	{
    		return false;
    	}
    	else
    	{
    		if (step==RulerNumber-1)
    		{
    			return true;
    		}
    	}

    	if (findRuler(step+1, current-rulers[step]))
    	{
    		choices[step]=-1;
    		return true;
    	}
    	else
    	{
    		if (findRuler(step+1, current+rulers[step]))
    		{
    			choices[step]=1;
    			return true;
    		}
    		else
    		{
    			return false;
    		}
    	}
    }

    How to run?

    You see the combination of recursion version. But for the dynamic programming version, there is only a true or

    false answer.

    rulers[0]=51
    rulers[1]=27
    rulers[2]=44
    rulers[3]=10
    rulers[4]=29
    rulers[5]=34
    rulers[6]=38
    rulers[7]=18
    rulers[8]=22
    rulers[9]=24
    rulers[10]=15
    rulers[11]=55
    rulers[12]=41
    rulers[13]=37
    rulers[14]=21
    input the length you want:79
    the choices is
    step0: -1 and position is: 28
    step1: -1 and position is: 1
    step2: 1 and position is: 45
    step3: -1 and position is: 35
    step4: -1 and position is: 6
    step5: 1 and position is: 40
    step6: -1 and position is: 2
    step7: 1 and position is: 20
    step8: 1 and position is: 42
    step9: -1 and position is: 18
    step10: -1 and position is: 3
    step11: 1 and position is: 58
    step12: -1 and position is: 17
    step13: 1 and position is: 54
    step14: 0 and position is: 54

    there is a solution for dynamic programming.
    Press any key to continue