Pocket Ruler
A. First Edition
This is another example of dynamic programming which is the question of assignment of comp465.
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 (thelengths of the
n consecutive rods) and a positive integer b (the depth ofyour 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 particularway will fit in your pocket if and only if there is an integer
s (representing theposition in your pocket where the beginning point of the ruler finds itself)
such that 0 <=
s <= b and0
<= 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 programMy 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.
¡¡
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