C++根据固定矩形大小装矩形的算法,箱子之间存在固定距离,源码
时间: 2024-03-01 09:50:08 浏览: 37
以下是一个简单的 C++ 实现,可以根据输入的固定矩形大小和箱子之间的固定距离,计算出最多可以装入多少个矩形,并输出放置后的矩形位置。
```c++
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct Rect {
int width, height;
int x, y;
};
bool cmp(Rect a, Rect b) {
return a.width * a.height > b.width * b.height;
}
bool canFit(Rect rect, Rect box, int gap) {
return rect.width <= box.width - gap && rect.height <= box.height - gap;
}
void place(Rect& rect, Rect& box, int gap) {
rect.x = box.x + gap;
rect.y = box.y + gap;
box.width -= rect.width + gap;
box.height -= rect.height + gap;
}
int packRects(vector<Rect>& rects, int boxWidth, int boxHeight, int gap) {
sort(rects.begin(), rects.end(), cmp);
vector<Rect> boxes;
boxes.push_back(Rect{boxWidth, boxHeight, 0, 0});
int count = 0;
for (auto& rect : rects) {
bool placed = false;
for (auto& box : boxes) {
if (canFit(rect, box, gap)) {
place(rect, box, gap);
placed = true;
break;
}
}
if (!placed) {
break;
}
count++;
}
for (auto& rect : rects) {
cout << "Rect [" << rect.width << ", " << rect.height << "] placed at (" << rect.x << ", " << rect.y << ")" << endl;
}
return count;
}
int main() {
vector<Rect> rects = {
{10, 20}, {20, 30}, {30, 10}, {10, 10}, {20, 20}, {10, 30}, {30, 30}
};
int boxWidth = 100;
int boxHeight = 100;
int gap = 5;
int count = packRects(rects, boxWidth, boxHeight, gap);
cout << "Total: " << count << endl;
return 0;
}
```
在这个实现中,我们使用了一个 `Rect` 结构体来表示矩形,在排序时按照矩形的面积从大到小排序。对于每个矩形,我们依次遍历所有箱子,找到可以容纳该矩形的箱子,并将矩形放置在该箱子中。如果所有箱子都无法容纳该矩形,则退出循环。
在放置矩形时,我们使用了一个 `place` 函数来计算矩形的位置,并更新箱子的大小。在计算位置时,我们需要考虑箱子之间的固定距离。最后,我们依次输出每个矩形的位置,并返回放置的矩形数量。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)