Solution Found!
Pebbling a checkerboard. We are given a checkerboard which has 4 rows and n columns
Chapter 6, Problem 6.5(choose chapter or problem)
Pebbling a checkerboard. We are given a checkerboard which has 4 rows and n columns, andhas an integer written in each square. We are also given a set of 2n pebbles, and we want toplace some or all of these on the checkerboard (each pebble can be placed on exactly one square)so as to maximize the sum of the integers in the squares that are covered by pebbles. There isone constraint: for a placement of pebbles to be legal, no two of them can be on horizontally orvertically adjacent squares (diagonal adjacency is fine).(a) Determine the number of legal patterns that can occur in any column (in isolation, ignoringthe pebbles in adjacent columns) and describe these patterns.Call two patterns compatible if they can be placed on adjacent columns to form a legal placement.Let us consider subproblems consisting of the first k columns 1 k n. Each subproblem canbe assigned a type, which is the pattern occurring in the last column.(b) Using the notions of compatibility and type, give an O(n)-time dynamic programming algorithmfor computing an optimal placement.
Questions & Answers
QUESTION:
Pebbling a checkerboard. We are given a checkerboard which has 4 rows and n columns, andhas an integer written in each square. We are also given a set of 2n pebbles, and we want toplace some or all of these on the checkerboard (each pebble can be placed on exactly one square)so as to maximize the sum of the integers in the squares that are covered by pebbles. There isone constraint: for a placement of pebbles to be legal, no two of them can be on horizontally orvertically adjacent squares (diagonal adjacency is fine).(a) Determine the number of legal patterns that can occur in any column (in isolation, ignoringthe pebbles in adjacent columns) and describe these patterns.Call two patterns compatible if they can be placed on adjacent columns to form a legal placement.Let us consider subproblems consisting of the first k columns 1 k n. Each subproblem canbe assigned a type, which is the pattern occurring in the last column.(b) Using the notions of compatibility and type, give an O(n)-time dynamic programming algorithmfor computing an optimal placement.
ANSWER:Step 1 of 5
A checkerboard with 4 rows and columns is given along with the pebbles. Dynamic programming is used for solving this problem. The checkerboard consists of rows and columns. With the given constraint, the objective is to find the legal patterns of pebbles that can be placed on the columns of the checkerboard.