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:

  1. There must be one cooler for every column in the grid.
  2. 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.
  3. 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

53.61% Correct | 46.39% Incorrect
Last Solution submitted on Mar 18, 2024

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers45

Suggested Problems

More from this Author19

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!