图论学习 c++长方体嵌套问题

一个长,宽,高为X1,X2,X3的长方体之中算法可以存放一个长,宽,高Y1,Y2,Y3的长方体。备注两个长方体都可以旋转,下面是一个C++程序,用于确定一个长方体是否可以放入另一个长方体中(备注:没有考虑全部情况),正确答案在第二段代码:

#include <iostream>
#include <algorithm>
#include <array>

// 函数声明
bool canFit(std::array<int, 3>& container, std::array<int, 3>& box);

int main() {
    // 定义容器(外部长方体)的尺寸
    std::array<int, 3> container;
    std::cout << "Enter container dimensions (length width height): ";
    std::cin >> container[0] >> container[1] >> container[2];

    // 定义要放入的盒子(内部长方体)的尺寸
    std::array<int, 3> box;
    std::cout << "Enter box dimensions (length width height): ";
    std::cin >> box[0] >> box[1] >> box[2];

    // 检查盒子是否可以放入容器
    if (canFit(container, box)) {
        std::cout << "The box can fit into the container." << std::endl;
    } else {
        std::cout << "The box cannot fit into the container." << std::endl;
    }

    return 0;
}

bool canFit(std::array<int, 3>& container, std::array<int, 3>& box) {
    // 对容器尺寸进行排序,从小到大
    std::sort(container.begin(), container.end());

    // 对盒子尺寸进行排序,从小到大
    std::sort(box.begin(), box.end());

    // 检查每个维度,盒子的尺寸是否小于等于容器的尺寸
    // 这里我们只需要检查排序后的对应维度,因为已经考虑了所有可能的旋转
    for (int i = 0; i < 3; ++i) {
        if (box[i] > container[i]) {
            return false;
        }
    }

    // 如果所有维度都符合要求,则盒子可以放入容器
    return true;
}

通过对尺寸进行排序,我们不需要显式地考虑所有可能的旋转。排序确保了我们总是在比较最小对最小,中等对中等,最大对最大的尺寸。如果这些配对都满足条件,那么就一定存在一种旋转方式使得盒子可以放入容器。

这个解决方案的时间复杂度是O(1),因为我们只处理固定数量(3个)的元素。空间复杂度也是O(1),因为我们使用的额外空间不随输入大小变化。

但是,请注意,长方体的长宽高是可以旋转的,当X1小于Y1,X2小于Y2,X3小于Y3时,两个长方体固然可以嵌套,但是如果X2小于Y1,X1小于Y2, X3小于Y3,他们依旧可以互相嵌套。

下面这个新版本的程序考虑了长方体所有可能的旋转情况。让我解释一下主要的变化:

  1. canFit 函数现在使用 const 引用来接收参数,因为我们不会修改原始数组。
  2. canFit 函数中,我们创建了一个 boxPermutation 数组来存储盒子尺寸的所有可能排列。
  3. 我们使用 std::next_permutation 函数来生成盒子尺寸的所有可能排列。这个函数会自动生成下一个字典序的排列。
  4. 对于每一种排列,我们检查是否可以放入容器。如果盒子的每个维度都小于或等于容器的对应维度,那么这种排列是可行的。
  5. 如果找到任何一种可行的排列,函数就返回 true
  6. 如果遍历完所有可能的排列都没有找到可行的方案,函数返回 false

这个新的实现考虑了长方体所有可能的旋转情况,包括您提到的例子(X2小于Y1,X1小于Y2,X3小于Y3)。它会检查盒子尺寸的所有6种可能排列(3!=6),确保不会遗漏任何可能的放置方式。

这个算法的时间复杂度是O(1),因为我们总是处理固定数量(3个)的元素,尽管我们检查了所有排列。空间复杂度也是O(1)。

#include <iostream>
#include <array>
#include <algorithm>

// 函数声明
bool canFit(const std::array<int, 3>& container, const std::array<int, 3>& box);

int main() {
    // 定义容器(外部长方体)的尺寸
    std::array<int, 3> container;
    std::cout << "Enter container dimensions (length width height): ";
    std::cin >> container[0] >> container[1] >> container[2];

    // 定义要放入的盒子(内部长方体)的尺寸
    std::array<int, 3> box;
    std::cout << "Enter box dimensions (length width height): ";
    std::cin >> box[0] >> box[1] >> box[2];

    // 检查盒子是否可以放入容器
    if (canFit(container, box)) {
        std::cout << "The box can fit into the container." << std::endl;
    } else {
        std::cout << "The box cannot fit into the container." << std::endl;
    }

    return 0;
}

bool canFit(const std::array<int, 3>& container, const std::array<int, 3>& box) {
    // 创建一个数组来存储盒子的所有可能排列
    std::array<int, 3> boxPermutation = box;

    // 使用do-while循环来生成所有可能的排列
    do {
        // 检查当前排列是否可以放入容器
        if (boxPermutation[0] <= container[0] &&
            boxPermutation[1] <= container[1] &&
            boxPermutation[2] <= container[2]) {
            return true;
        }
    } while (std::next_permutation(boxPermutation.begin(), boxPermutation.end()));

    // 如果所有排列都不能放入,返回false
    return false;
}

上一篇:AI+3D生成的创新前沿:基于大模型的3D人体动作生成框架前瞻


下一篇:C++ 预处理器定义