logo

TechCodeview

Папир исечен на минимални број квадрата

Дат правоугаони папир димензија а к б . Задатак је да исечете цео папир у минимум број од квадратни комада. Можемо изабрати квадратне комаде било које величине, али они морају бити исечени без преклапања или остављања додатног простора .

Примери:  

Улаз: а = 5 б = 8



јава боолеан
Папир-изрезан на-минимални-број-квадрата-1' title=5 квадрата исечених од папира величине 5 Кс 8

Излаз: 5
Објашњење: Папир можемо исећи на 5 квадрата: 1 квадрат величине 5к5, 1 квадрат величине 3к3, 1 квадрат величине 2к2 и 2 квадрата величине 1к1.

Улаз: а = 13 б = 11

Папир-изрезан на-минимални-број-квадрата-2' loading='lazy' title=6 квадрата исечених од папира величине 13 Кс 11

Излаз: 6
Објашњење: Папир можемо исећи на 6 квадрата: 1 квадрат величине 7к7 1 квадрат величине 6к6 1 квадрат величине 5к5 2 квадрата величине 4к4 и 1 квадрат величине 1к1.

Улаз: а = 6 б = 7

Папир-изрезан на-минимални-број-квадрата-3' loading='lazy' title=5 квадрата исечених од папира величине 6 Кс 7

Излаз: 5
Објашњење: Папир можемо исећи на 5 квадрата: 1 квадрат величине 4к4, 2 квадрата величине 3к3 и 2 квадрата величине 3к3.

Садржај

[Нетачан приступ 1] Коришћење похлепне технике

На први поглед може изгледати да се проблем може лако решити тако што се из папира прво исече највећи могући квадрат, а затим од преосталог папира исече се највећи квадрат и тако све док не исечемо цео папир. Али ово решење је нетачно.

Зашто похлепни приступ неће радити?

Размотрите папир величине 6к7 онда ако покушамо да похлепно исечемо папир добићемо 7 квадрати: 1 квадрат величине 6к6 и 6 квадрата величине 1к1 док је исправно решење: 5. Стога похлепни приступ неће радити.

јава цаст стринг у инт

[Нетачан приступ 2] Коришћење динамичког програмирања

Динамичко програмирање са вертикалним или хоризонталним резовима: Још једно решење које би могло изгледати исправно је коришћење Динамичко програмирање . Можемо одржавати табелу дп[][] тако да дп[и][ј] = минимални број квадрата који се могу исећи од папира величине и к ј . Затим за папир величине акб

  • Можемо покушати да га исечемо дуж сваког реда: дп[и][ј] = мин(дп[и][ј] 1 + дп[и - к][ј] + дп[к][ј]) где к може бити у опсегу [1 и - 1].
  • Можемо покушати да га исечемо дуж сваке колоне: дп[и][ј] = мин(дп[и][ј] 1 + дп[и][ј - к] + дп[и][к]) где к може бити у опсегу [1 ј - 1].

Коначно, одговор ће бити минимум свих резова. Али ово решење је такође нетачно.

Зашто вертикално или хоризонтално сечење помоћу приступа динамичком програмирању неће радити?

Ово неће функционисати јер претпостављамо да ће вертикални или хоризонтални рез увек поделити правоугаоник на два дела. Размотрите папир величине 13к11 онда ако покушамо да исечемо папир користећи ДП приступ добићемо 8 квадрата, али тачан одговор (као што је приказано у примерима) је 6. Стога динамичко програмирање неће радити.

[Тачан приступ] Коришћење ДФС-а и динамичког програмирања

Тхе идеја је да исечете цео папир користећи ДФС ин одоздо према горе начин. У сваком кораку пронађите доњи леви угао папира и покушајте да исечете квадрате свих могућих величина из тог угла. Након што поново исечете квадрат, пронађите доњи леви угао преосталог папира да исечете квадрате свих могућих величина и тако даље. Али ако покушамо све могуће резове из најнижег левог угла сваке могуће величине папира, онда би то било прилично неефикасно. Можемо га оптимизовати коришћењем Динамичко програмирање да сачувате минималне резове за сваку могућу величину папира.

Да бисмо јединствено идентификовали било коју величину папира, можемо одржавати ремСк[] низ тако да ремСк[и] складишти број преосталих квадрата величине 1к1 у и-тој колони папира. Дакле, за папир величине 6к7 ремСк[] = {6 6 6 6 6 6 6}. Такође да бисмо пронашли најнижи леви угао, наћи ћемо први индекс који има највише преосталих квадрата. Дакле, можемо хеширати вредност ремСк[] низа да бисмо пронашли јединствени кључ за све могуће вредности низа ремСк[].

C++ 
// C++ Program to find minimum number of squares to cut // from a paper of size axb #include    using namespace std; // function to get the hash key for remSq array int getKey(vector<int> &remSq int b) {  int base = 1;  int key = 0;  for (int i = 0; i < b; i++)  {  key += (remSq[i] * base);  base = base * (b + 1);  }  return key; } // Recursive function to find the minimum number of square cuts // for a given remSq array int minCutUtil(vector<int> &remSq int a int b   map<int int> &memo) {  // pointers to mark the start and end of range   // with maximum remaining squares  int start end;  // Check if we have previously calculated the answer  // for the same state  int key = getKey(remSq b);  if (memo.find(key) != memo.end())  return memo[key];  int maxRemSq = 0;  // Find the starting point of min height  for (int i = 0; i < b; i++) {  if (remSq[i] > maxRemSq) {  maxRemSq = remSq[i];  start = i;  }  }  // If max remaining squares = 0 then we have already  // cut the entire paper  if (maxRemSq == 0)  return 0;  end = start;  vector<int> newRemSq = remSq;  int ans = INT_MAX;  // Find the ending point of min height  while (end < b) {  // length of edge of square from start till current end  int squareEdge = end - start + 1;  // If the current column does not have maximum remaining  // squares or if it's impossible to cut a square of  // size squareEdge then break out of the loop  if (newRemSq[end] != maxRemSq ||   newRemSq[end] - squareEdge < 0)  break;  // If we can cut a square of size squareEdge   // update the remainingSquares  for (int i = start; i <= end; i++)  newRemSq[i] = maxRemSq - squareEdge;  // Find the solution for new remainingSquares  ans = min(ans 1 + minCutUtil(newRemSq a b memo));  end += 1;  }  return memo[key] = ans; } // Function to find the minimum number of squares we can cut  // using paper of size a X b int minCut(int a int b) {  // if the given rectangle is a square  if (a == b)  return 1;  // Initialize remaining squares = a for all the b columns  vector<int> remSq(b a);  map<int int> memo;  return minCutUtil(remSq a b memo); } int main() {  // Sample Input  int a = 13 b = 11;  // Function call to get minimum number   // of squares for axb  cout << minCut(a b);  return 0; }
Java 
// Java Program to find minimum number of squares to cut // from a paper of size axb import java.util.*; class GfG {  // function to get the hash key for remSq array  static int getKey(int[] remSq int b) {  int base = 1;  int key = 0;  for (int i = 0; i < b; i++) {  key += (remSq[i] * base);  base = base * (b + 1);  }  return key;  }  // Recursive function to find the minimum number of square cuts  // for a given remSq array  static int minCutUtil(int[] remSq int a int b  Map<Integer Integer> memo) {  // pointers to mark the start and end of range   // with maximum remaining squares  int start = 0 end;  // Check if we have previously calculated the answer  // for the same state  int key = getKey(remSq b);  if (memo.containsKey(key))  return memo.get(key);  int maxRemSq = 0;  // Find the starting point of min height  for (int i = 0; i < b; i++) {  if (remSq[i] > maxRemSq) {  maxRemSq = remSq[i];  start = i;  }  }  // If max remaining squares = 0 then we have already  // cut the entire paper  if (maxRemSq == 0)  return 0;  end = start;  int[] newRemSq = Arrays.copyOf(remSq b);  int ans = Integer.MAX_VALUE;  // Find the ending point of min height  while (end < b) {  // length of edge of square from start till current end  int squareEdge = end - start + 1;  // If the current column does not have maximum remaining  // squares or if it's impossible to cut a square of  // size squareEdge then break out of the loop  if (newRemSq[end] != maxRemSq ||  newRemSq[end] - squareEdge < 0)  break;  // If we can cut a square of size squareEdge   // update the remainingSquares  for (int i = start; i <= end; i++)  newRemSq[i] = maxRemSq - squareEdge;  // Find the solution for new remainingSquares  ans = Math.min(ans 1 + minCutUtil(newRemSq a b memo));  end += 1;  }  memo.put(key ans);  return ans;  }  // Function to find the minimum number of squares we can cut   // using paper of size a X b  static int minCut(int a int b) {  // if the given rectangle is a square  if (a == b)  return 1;  // Initialize remaining squares = a for all the b columns  int[] remSq = new int[b];  Arrays.fill(remSq a);  Map<Integer Integer> memo = new HashMap<>();  return minCutUtil(remSq a b memo);  }  public static void main(String[] args) {  // Sample Input  int a = 13 b = 11;  // Function call to get minimum number   // of squares for axb  System.out.println(minCut(a b));  } }
Python 
# Python Program to find minimum number of squares to cut # from a paper of size axb # function to get the hash key for remSq array def getKey(remSq b): base = 1 key = 0 for i in range(b): key += remSq[i] * base base = base * (b + 1) return key # Recursive function to find the minimum number of square cuts # for a given remSq array def minCutUtil(remSq a b memo): # pointers to mark the start and end of range  # with maximum remaining squares start = 0 # Check if we have previously calculated the answer # for the same state key = getKey(remSq b) if key in memo: return memo[key] maxRemSq = 0 # Find the starting point of min height for i in range(b): if remSq[i] > maxRemSq: maxRemSq = remSq[i] start = i # If max remaining squares = 0 then we have already # cut the entire paper if maxRemSq == 0: return 0 end = start newRemSq = remSq[:] ans = float('inf') # Find the ending point of min height while end < b: # length of edge of square from start till current end squareEdge = end - start + 1 # If the current column does not have maximum remaining # squares or if it's impossible to cut a square of # size squareEdge then break out of the loop if newRemSq[end] != maxRemSq or  newRemSq[end] - squareEdge < 0: break # If we can cut a square of size squareEdge  # update the remainingSquares for i in range(start end + 1): newRemSq[i] = maxRemSq - squareEdge # Find the solution for new remainingSquares ans = min(ans 1 + minCutUtil(newRemSq a b memo)) end += 1 memo[key] = ans return ans # Function to find the minimum number of squares we can cut  # using paper of size a X b def minCut(a b): # if the given rectangle is a square if a == b: return 1 # Initialize remaining squares = a for all the b columns remSq = [a] * b memo = {} return minCutUtil(remSq a b memo) if __name__ == '__main__': # Sample Input a = 13 b = 11 # Function call to get minimum number  # of squares for axb print(minCut(a b))
C# 
// C# Program to find minimum number of squares to cut // from a paper of size axb using System; using System.Collections.Generic; class GfG {  // function to get the hash key for remSq array  static int getKey(int[] remSq int b) {  int baseVal = 1;  int key = 0;  for (int i = 0; i < b; i++) {  key += (remSq[i] * baseVal);  baseVal = baseVal * (b + 1);  }  return key;  }  // Recursive function to find the minimum number of square cuts  // for a given remSq array  static int minCutUtil(int[] remSq int a int b  Dictionary<int int> memo) {  // pointers to mark the start and end of range   // with maximum remaining squares  int start = 0 end;  // Check if we have previously calculated the answer  // for the same state  int key = getKey(remSq b);  if (memo.ContainsKey(key))  return memo[key];  int maxRemSq = 0;  // Find the starting point of min height  for (int i = 0; i < b; i++) {  if (remSq[i] > maxRemSq) {  maxRemSq = remSq[i];  start = i;  }  }  // If max remaining squares = 0 then we have already  // cut the entire paper  if (maxRemSq == 0)  return 0;  end = start;  int[] newRemSq = (int[])remSq.Clone();  int ans = int.MaxValue;  // Find the ending point of min height  while (end < b) {  // length of edge of square from start till current end  int squareEdge = end - start + 1;  // If the current column does not have maximum remaining  // squares or if it's impossible to cut a square of  // size squareEdge then break out of the loop  if (newRemSq[end] != maxRemSq ||  newRemSq[end] - squareEdge < 0)  break;  // If we can cut a square of size squareEdge   // update the remainingSquares  for (int i = start; i <= end; i++)  newRemSq[i] = maxRemSq - squareEdge;  // Find the solution for new remainingSquares  ans = Math.Min(ans 1 + minCutUtil(newRemSq a b memo));  end += 1;  }  memo[key] = ans;  return ans;  }  // Function to find the minimum number of squares we can cut   // using paper of size a X b  static int minCut(int a int b) {  // if the given rectangle is a square  if (a == b)  return 1;  // Initialize remaining squares = a for all the b columns  int[] remSq = new int[b];  for (int i = 0; i < b; i++) remSq[i] = a;  Dictionary<int int> memo = new Dictionary<int int>();  return minCutUtil(remSq a b memo);  }  static void Main() {  int a = 13 b = 11;  // Function call to get minimum number   // of squares for axb  Console.WriteLine(minCut(a b));  } }
JavaScript 
// JavaScript Program to find minimum number of squares to cut // from a paper of size axb // function to get the hash key for remSq array function getKey(remSq b) {  let base = 1;  let key = 0;  for (let i = 0; i < b; i++) {  key += (remSq[i] * base);  base = base * (b + 1);  }  return key; } // Recursive function to find the minimum number of square cuts // for a given remSq array function minCutUtil(remSq a b memo) {  // pointers to mark the start and end of range   // with maximum remaining squares  let start = 0 end;  // Check if we have previously calculated the answer  // for the same state  let key = getKey(remSq b);  if (key in memo)  return memo[key];  let maxRemSq = 0;  // Find the starting point of min height  for (let i = 0; i < b; i++) {  if (remSq[i] > maxRemSq) {  maxRemSq = remSq[i];  start = i;  }  }  // If max remaining squares = 0 then we have already  // cut the entire paper  if (maxRemSq === 0)  return 0;  end = start;  let newRemSq = remSq.slice();  let ans = Infinity;  // Find the ending point of min height  while (end < b) {  // length of edge of square from start till current end  let squareEdge = end - start + 1;  // If the current column does not have maximum remaining  // squares or if it's impossible to cut a square of  // size squareEdge then break out of the loop  if (newRemSq[end] !== maxRemSq ||  newRemSq[end] - squareEdge < 0)  break;  // If we can cut a square of size squareEdge   // update the remainingSquares  for (let i = start; i <= end; i++)  newRemSq[i] = maxRemSq - squareEdge;  // Find the solution for new remainingSquares  ans = Math.min(ans 1 + minCutUtil(newRemSq a b memo));  end += 1;  }  memo[key] = ans;  return ans; } // Function to find the minimum number of squares we can cut  // using paper of size a X b function minCut(a b) {  // if the given rectangle is a square  if (a === b)  return 1;  // Initialize remaining squares = a for all the b columns  let remSq = new Array(b).fill(a);  let memo = {};  return minCutUtil(remSq a b memo); } // Driver Code let a = 13 b = 11; // Function call to get minimum number  // of squares for axb console.log(minCut(a b));

Излаз 
6

Временска сложеност: О(а^б) за сваку од б колона можемо имати квадрате.
Помоћни простор: О(а^б) због меморисања чувања сваког јединственог стања.