Problem 45415. Find an optimal placement of coolers on a grid
In a certain chemical plant, 6 new pieces of cooling equipment (coolers) are to be installed in a vacant space. This vacant space was divided into a grid of 6 cells by 6 cells. Your task is to assign the 6 coolers to 6 cells in this grid with the following requirements:
- There must be one cooler for every column in the grid.
- If you decide to install a cooler at row R, column C, then the cooler at column C+1 must be installed either on row R-1, R, or R+1 only. This is done to ease the connection of coolers by piping.
- The total installation cost for the 6 coolers must be minimum.
For this problem, you are given a cost matrix (COST) in relation to the third requirement above. COST is a 6 x 6 matrix where the r,c-th element is the cost of assigning any cooler to row r, column c (All the coolers are identical). Write a function that accepts the matrix COST, and output the value of the minimum cost of installation. You are ensured that all elements of COST are integers in the range [1,1000].
In the sample test case below, the optimal placement is at the following rows: 4,3,3,2,2,2.
>> COST = [695 766 710 119 752 548; 318 796 755 499 256 139; 951 187 277 960 506 150; 35 490 680 341 700 258; 439 446 656 586 891 841; 382 647 163 224 960 255]; >> coolers(COST) ans = 1393
Meanwhile, the optimal placement for the case below is at rows: 5,6,5,6,5,6
>> COST = [815 617 918 76 569 312; 244 474 286 54 470 529; 930 352 758 531 455 988; 350 831 754 780 12 602; 197 586 381 935 163 263; 252 550 568 130 795 100]; >> coolers(COST) ans = 1521
Solution Stats
Problem Comments
-
2 Comments
nice problem (hint: viterbi) and overall an excellent series / problem-group!
I wish I had done a clever solution but I resorted to brute forcing it!
Solution Comments
Show commentsProblem Recent Solvers47
Suggested Problems
-
15694 Solvers
-
Find all elements less than 0 or greater than 10 and replace them with NaN
15487 Solvers
-
Project Euler: Problem 8, Find largest product in a large string of numbers
1082 Solvers
-
Return unique values without sorting
909 Solvers
-
Is this triangle right-angled?
5670 Solvers
More from this Author19
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!