Lab 5 – Using Dynamic Programming in the gallery

Github Classroom

Below are three DP-solvable subproblems that map cleanly onto the art exhibition layout project. You will be assigned a team to worm on this with.

Lab 1 — Room Wall-Space Selection (0/1 Knapsack)

Problem (exhibition framing)

You have one room with a fixed amount of usable wall length (after doors/windows). You must choose which wall-hung artworks to include. Each artwork consumes wall length (including required clearance) and has a “curatorial value” score.

Goal: maximize total value without exceeding wall length.

This is exactly 0/1 knapsack:

capacity = wall length
weight = artwork width (with clearance)
value = curatorial value

DP definition

Let items be 1..n. Capacity is 0..W.

dp[i][w] = best value using first i artworks with wall capacity w
Recurrence:
- If artwork i has width w_i and value v_i:
- dp[i][w] = dp[i-1][w] (skip)
- If w_i <= w: dp[i][w] = max(dp[i][w], dp[i-1][w-w_i] + v_i) (take)

Small dataset (do in class, show full table)

Wall capacity W = 10

Artwork	Width	Value
A	2	3
B	3	4
C	4	5
D	5	8

DP table (values), rows = i (0..4), cols = w (0..10)

i \ w	2	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	0
1 (A)	3	3	3	3	3	3	3	3	3
2 (B)	3	4	4	7	7	7	7	7	7
3 (C)	3	4	5	7	8	9	9	12	12
4 (D)	3	4	5	8	8	11	12	13	15

Optimal value = 15 at capacity 10.

Example “equation under the table” you can require on each step:

For item D (w=5, v=8) at capacity 10:
dp[4][10] = max(dp[3][10], dp[3][10-5] + 8) = max(12, 7 + 8) = 15

Larger dataset (for grading / testing)

Wall capacity W = 40

Artwork	Width	Value
P1	6	14
P2	9	18
P3	7	13
P4	5	10
P5	12	25
P6	10	20
P7	4	8
P8	8	15
P9	11	19
P10	3	6
P11	13	26
P12	2	4

Deliverables:

dp table for the small dataset (full grid)
code that solves the large dataset + prints chosen artworks (backtracking)

Lab 2 — Panel / Wall-Segment Packing (“Word Wrap” DP)

Problem (exhibition framing)

You have a corridor (or a room) with a sequence of wall panels/segments each of length L. You must place artworks in a fixed order (curatorial narrative order, or physical walking order). You decide where to break between panels.

You want to avoid ugly gaps. Penalize unused space on each panel.

Goal: minimize total penalty.

This is classic text justification / word wrap DP.

DP definition

Given widths w₁..w_n, panel length L.

Define the cost of placing artworks i..j on one panel:

if sum(w_i..w_j) > L: cost = ∞ (doesn’t fit)
else cost = (L - sum(w_i..w_j))^2
(often make the last panel cost = 0)

Then:

dp[j] = min penalty to place artworks 1..j
recurrence:
- dp[j] = min over i=1..j ( dp[i-1] + cost(i, j) )

Small dataset (compute full cost matrix + dp)

Panel length L = 10
Artworks must stay in this order:

#	Width
1	2
2	5
3	3
4	4
5	2

Cost table sample (cost(i,j)) (∞ means “doesn’t fit”):

i\j	1	2	3	4	5
1	(10-2)²=64	(10-7)²=9	(10-10)²=0	∞	∞
2		(10-5)²=25	(10-8)²=4	∞	∞
3			(10-3)²=49	(10-7)²=9	(10-9)²=1
4				(10-4)²=36	(10-6)²=16
5					(10-2)²=64

Now compute dp (with last panel cost forced to 0):

dp[0]=0
dp[1]=64
dp[2]=9 (1..2 fits with penalty 9)
dp[3]=0 (1..3 fits perfectly: penalty 0)
dp[4]=18 (best is [1..2] penalty 9 + [3..4] penalty 9)
dp[5]=0 (best is [1..3] penalty 0 + [4..5] last panel cost 0)

So the optimal breaks are:

Panel 1: artworks 1–3 (2+5+3=10)
Panel 2: artworks 4–5 (4+2=6) (last panel → cost 0)

Deliverables:

Fill the full cost(i,j) table for the small dataset
Fill dp[0..n] and reconstruct the breaks
Implement for large dataset

Larger dataset (for grading / testing)

Panel length L = 24
Widths (fixed order):
[6, 7, 5, 8, 4, 9, 3, 7, 6, 5, 4, 8, 6, 3]

Ask them to print:

minimum total penalty
the panel breaks (which artworks on each panel)

Lab 3 — Two-Room Allocation (2-Knapsack DP)

Problem (exhibition framing)

You have two rooms, each with a wall-length budget. Each artwork can be hung in Room A, Room B, or not displayed. (Still 0/1 per artwork.)

Goal: maximize total curatorial value subject to both room capacities.

This is a clean DP that feels like “layout across rooms” without getting into full NP-hard multi-room assignment.

DP definition

Capacities: CA and CB.

Let:

dp[a][b] = best value achievable with Room A capacity a and Room B capacity b after processing some prefix of artworks.

For each artwork (width w, value v), update:

skip: dp[a][b] stays
place in A if w<=a: candidate dp[a-w][b] + v
place in B if w<=b: candidate dp[a][b-w] + v

(Implementation usually loops items outermost and updates into a new table, or updates in reverse.)

Small dataset (show full dp grid)

Capacities: CA=6, CB=7

Artwork	Width	Value
P1	2	6
P2	3	5
P3	4	8
P4	5	9
P5	1	3

Final dp[a][b] table (rows a=0..6, cols b=0..7):

a\b	0	1	2	3	4	5	6	7
0	0	3	6	9	9	11	14	17
1	3	3	9	9	11	14	17	18
2	6	9	9	11	14	17	18	19
3	9	9	11	14	17	18	19	22
4	9	11	14	17	17	19	22	23
5	11	14	17	18	19	22	23	26
6	14	17	18	19	22	23	26	26

Optimal value is 26.

Example “equation under the table” for one update (placing P4, w=5, v=9):

At state (a=6,b=7):
dp'[6][7] = max(dp[6][7], dp[6-5][7] + 9, dp[6][7-5] + 9)

Deliverables:

Produce the dp grid for the small dataset (exactly)
Backtrack (or store choices) to output which room each chosen artwork went to
Implement for large dataset

Larger dataset (for grading / testing)

Capacities: CA=20, CB=18

Artwork	Width	Value
A1	6	14
A2	7	16
A3	5	11
A4	9	19
A5	4	9
A6	8	17
A7	3	7
A8	10	22
A9	2	5
A10	6	13
A11	7	15
A12	5	12

Require:

maximum total value
assignment list: A / B / not shown

If you want, I can also format each lab into a one-page student handout with: background story, explicit inputs/outputs, starter pseudocode, and a rubric aligned with “full credit for any reasonable solution + correct DP table + correct reconstruction.”