矩形切割:不同规格的小矩形 随机挑选然后放到一个大矩形上面,要求大矩形的占用率最高,有什么算法?

这是一个经典的二维装箱问题，可以使用贪心算法或者动态规划算法来解决。

1. 贪心算法

贪心算法的思路是每次选择剩余矩形中最大的一个能够放得下的矩形，然后将其放置在大矩形中占用最小的位置。这个过程重复进行，直到所有小矩形都被放置。具体实现可以使用排序和遍历来寻找最优解。

2. 动态规划算法

动态规划算法的思路是将大矩形划分成多个小矩形，然后构建一个二维数组来记录每个小矩形的放置情况。具体实现可以使用回溯或者递归来寻找最优解，但是这种算法往往需要更多的时间和空间。

总之，矩形切割问题的解决方法有很多种，需要结合具体情况来选择适合的算法。

相关问题

C++2D矩形装箱算法，给定矩形边界大小，和指定间隙距离，多个矩形输入装箱，利用率最高的排版算法代码

这里提供一个基于贪心算法的C++2D矩形装箱算法，可以实现多个矩形的高效排版。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Rect {
    int id, w, h, x, y;
    Rect(int _id, int _w, int _h) {
        id = _id;
        w = _w;
        h = _h;
        x = y = 0;
    }
};

bool cmp(Rect a, Rect b) {
    if (a.h != b.h) return a.h > b.h;
    return a.w > b.w;
}

class Bin {
public:
    int w, h;
    vector<Rect> rects;
    Bin(int _w, int _h) {
        w = _w;
        h = _h;
    }

    bool add(Rect rect) {
        int x = 0, y = 0;
        if (!find_pos(rect, x, y)) return false;
        rect.x = x;
        rect.y = y;
        rects.push_back(rect);
        return true;
    }

private:
    bool find_pos(Rect rect, int& x, int& y) {
        sort(rects.begin(), rects.end(), cmp);
        for (int i = 0; i < rects.size(); i++) {
            if (rect.w <= w - rects[i].x && rect.h <= h - rects[i].y) {
                x = rects[i].x;
                y = rects[i].y;
                for (int j = i + 1; j < rects.size(); j++) {
                    if (rects[j].y < y + rect.h && rects[j].x < x + rect.w) {
                        x = max(x, rects[j].x + rects[j].w);
                    }
                }
                return true;
            } else if (rect.h <= w - rects[i].y && rect.w <= h - rects[i].x) {
                swap(w, h);
                for (int j = 0; j < rects.size(); j++) {
                    if (rects[j].y < x + rect.w && rects[j].x < y + rect.h) {
                        y = max(y, rects[j].y + rects[j].h);
                    }
                }
                swap(w, h);
                swap(rect.w, rect.h);
                swap(x, y);
                if (find_pos(rect, x, y)) return true;
            }
        }
        return false;
    }
};

bool cmp_area(Rect a, Rect b) {
    return a.w * a.h > b.w * b.h;
}

vector<Rect> pack_rects(int w, int h, vector<Rect>& rects) {
    vector<Rect> result;
    sort(rects.begin(), rects.end(), cmp_area);
    Bin bin(w, h);
    for (int i = 0; i < rects.size(); i++) {
        if (!bin.add(rects[i])) {
            cout << "Can not pack rectangle " << rects[i].id << endl;
        } else {
            result.push_back(rects[i]);
        }
    }
    return result;
}

int main() {
    int w = 100, h = 100, gap = 5;
    vector<Rect> rects;
    rects.push_back(Rect(1, 20, 30));
    rects.push_back(Rect(2, 30, 40));
    rects.push_back(Rect(3, 25, 25));
    rects.push_back(Rect(4, 15, 20));
    rects.push_back(Rect(5, 10, 30));
    rects.push_back(Rect(6, 10, 10));
    rects.push_back(Rect(7, 40, 30));
    vector<Rect> result = pack_rects(w - gap * 2, h - gap * 2, rects);
    for (int i = 0; i < result.size(); i++) {
        cout << "Rectangle " << result[i].id << " (" << result[i].w << ", " << result[i].h << ") at (" << result[i].x + gap << ", " << result[i].y + gap << ")" << endl;
    }
    return 0;
}

这个算法的实现思想是先按照面积大小对矩形进行排序，然后按照贪心策略依次将矩形装入最佳位置。装箱时，按照矩形高度和宽度的大小排序，并从大到小遍历已经排好的矩形，寻找可以放置当前矩形的最佳位置。

具体实现中，我们使用 `Bin` 类来表示一个装箱盒子，其中包含了当前盒子的宽度和高度，以及已经放置的矩形列表。对于每个 `Rect` 矩形，我们从已经放置的矩形中寻找可以放置它的最佳位置，并将它放置在这个位置上。如果找不到合适的位置，则说明当前盒子已经装不下这个矩形了。

最终，我们返回已经放置的矩形列表，这些矩形的坐标信息都已经被计算好了。

c语言将矩形分成多个小正方形,蓝桥杯练习算法题（矩形切割成正方形）

这道题目可以使用贪心算法来解决。

首先，我们可以将矩形的长和宽取最大公约数，因为只有最大公约数的倍数才能够被等分成相等的小正方形。

然后，我们可以将矩形的长和宽都除以最大公约数，得到一个新的矩形，它的长和宽都是最大公约数的倍数。

接下来，我们可以用一个循环来不断地将这个新的矩形切割成正方形，每次切割的大小都是矩形较小的一边。如果切割后还剩下一个矩形，我们可以将它的长和宽再次除以最大公约数，得到一个新的矩形，然后继续切割。

最后，当矩形被切割成了所有相等的小正方形时，算法结束。

下面是使用C语言实现的代码：

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    int w, h;
    scanf("%d %d", &w, &h);
    int d = gcd(w, h);
    int n = w / d;
    int m = h / d;
    int ans = n * m;
    printf("%d\n", ans);
    return 0;
}

在这个程序中，我们首先输入矩形的长和宽，然后求出它们的最大公约数d。接着，我们将矩形的长和宽都除以d，得到一个新的矩形，它的长和宽都是d的倍数。然后，我们计算这个新的矩形可以被切割成的正方形的个数，即n乘以m。最后，输出答案即可。