資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中將木板切割成正方形的最小成本
概念
假設給定一塊長為 p、寬為 q 的木板，我們需要將其切割成 p*q 個正方形，使得切割成本最小。對於這塊木板，每條邊的切割成本將被給出。簡而言之，我們需要選擇一個切割序列，使得成本最小化。
示例
關於上述木板，將其切割成正方形的最佳方式是：
上述情況下的總最小成本為 65。它是透過實現以下步驟計算得出的。
Initial Value : Total_cost = 0 Total_cost = Total_cost + edge_cost * total_pieces Cost 5 Horizontal cut Cost = 0 + 5*1 = 5 Cost 5 Vertical cut Cost = 5 + 5*2 = 15 Cost 4 Vertical cut Cost = 15 + 4*2 = 23 Cost 3 Horizontal cut Cost = 23 + 3*3 = 32 Cost 3 Vertical cut Cost = 32 + 3*3 = 41 Cost 2 Horizontal cut Cost = 41 + 2*4 = 49 Cost 2 Vertical cut Cost = 49 + 2*4 = 57 Cost 2 Vertical cut Cost = 57 + 2*4 = 65
方法
這種型別的問題可以透過實現貪婪演算法來解決。如果總成本用 S 表示，則 S = b1x1 + b2x2 … + bkxk，其中 xi 表示某條邊切割的成本，bi 是相應的係數，係數 bi 由我們在切割過程結束時透過邊 xi 完成的切割總數決定。
我們應該注意到係數的總和始終是常數，因此我們希望計算出可獲得的 bi 分佈，使得 S 最小。為此，我們儘快在最大成本邊上進行切割，這將達到最佳的 S。如果我們遇到幾條具有相同成本的邊，我們可以先移除或切割其中任何一條。
C++ 程式
以下是實現上述方法的解決方案，我們首先按降序對邊切割成本進行排序，然後從較高成本到較低成本迴圈遍歷它們，構建我們的解決方案。每次我們選擇一條邊，對應的計數都會增加 1，這將每次乘以相應的邊切割成本。
示例
// C++ program to divide a board into p*q squares
#include <bits/stdc++.h>
using namespace std;
int minimumCostOfBreaking(int X1[], int Y1[], int p, int q){
int res1 = 0;
sort(X1, X1 + p, greater<int>());
sort(Y1, Y1 + q, greater<int>());
int hzntl = 1, vert = 1;
int i = 0, j = 0;
while (i < p && j < q){
if (X1[i] > Y1[j]){
res1 += X1[i] * vert;
hzntl++;
i++;
}
else{
res1 += Y1[j] * hzntl;
vert++;
j++;
}
}
int total = 0;
while (i < p)
total += X1[i++];
res1 += total * vert;
total = 0;
while (j < q)
total += Y1[j++];
res1 += total * hzntl;
return res1;
}
int main(){
int p = 6, q = 4;
int X1[p-1] = {3, 2, 4, 2, 5};
int Y1[q-1] = {5, 2, 3};
cout << minimumCostOfBreaking(X1, Y1, p-1, q-1);
return 0;
}輸出
65
更新於： 2020-07-23
288 次瀏覽
廣告