当前位置: 面试刷题>> 木材加工 (经典算法题500道)


题目描述补充

木材加工问题

假设你是一家木材加工厂的管理者,你需要根据客户的订单要求,将原木切割成指定长度的木段。每根原木的长度是固定的,但不同订单要求的木段长度可能不同。你的任务是编写一个算法,以最小化原木的使用数量,并满足所有订单需求。

输入

  1. 原木的长度(一个整数)。
  2. 一个订单列表,每个订单包含需要的木段长度和数量(以二维数组或列表的列表形式给出)。

输出

  1. 所需的最少原木数量以满足所有订单。

示例

  • 原木长度:10
  • 订单列表:[[2, 5], [4, 2], [3, 3]]
    • 这意味着需要5段长度为2的木段,2段长度为4的木段,和3段长度为3的木段。

注意:切割时不允许拼接木段,且原木长度足够大,至少能满足一个订单需求。

示例代码

PHP 示例

function minLogs($logLength, $orders) {
    $logsUsed = 0;
    $currentLog = [];

    while (!empty($orders)) {
        $currentLog = [];
        $logsUsed++;

        foreach ($orders as $index => $order) {
            $length = $order[0];
            $quantity = $order[1];

            while ($quantity > 0 && $logLength >= $length) {
                $currentLog[] = $length;
                $logLength -= $length;
                $quantity--;

                if ($quantity === 0) {
                    unset($orders[$index]);
                }
            }

            if ($quantity > 0) {
                // 如果还有剩余需求,则订单重新加入列表,但减少已满足的数量
                $orders[$index][1] = $quantity;
            }
        }

        // 清理已完成的订单
        $orders = array_values(array_filter($orders));
    }

    return $logsUsed;
}

// 示例使用
$logLength = 10;
$orders = [[2, 5], [4, 2], [3, 3]];
echo minLogs($logLength, $orders); // 输出结果

Python 示例

def min_logs(log_length, orders):
    logs_used = 0
    while orders:
        current_log = []
        logs_used += 1
        remaining_length = log_length
        
        i = 0
        while i < len(orders):
            length, quantity = orders[i]
            while quantity > 0 and remaining_length >= length:
                current_log.append(length)
                remaining_length -= length
                quantity -= 1
                
            if quantity == 0:
                del orders[i]
            else:
                i += 1
        
    return logs_used

# 示例使用
log_length = 10
orders = [[2, 5], [4, 2], [3, 3]]
print(min_logs(log_length, orders))  # 输出结果

JavaScript 示例

function minLogs(logLength, orders) {
    let logsUsed = 0;
    while (orders.length > 0) {
        let currentLog = [];
        logsUsed++;
        let remainingLength = logLength;

        for (let i = 0; i < orders.length; ) {
            const [length, quantity] = orders[i];
            while (quantity > 0 && remainingLength >= length) {
                currentLog.push(length);
                remainingLength -= length;
                quantity--;

                if (quantity === 0) {
                    orders.splice(i, 1);
                } else {
                    i++;
                }
            }

            if (quantity > 0) {
                // 如果未完全满足,则不移动索引i,继续下一轮循环处理
            }
        }
    }

    return logsUsed;
}

// 示例使用
const logLength = 10;
const orders = [[2, 5], [4, 2], [3, 3]];
console.log(minLogs(logLength, orders)); // 输出结果

码小课:在码小课网站上,你可以找到更多关于算法和数据结构的知识分享,帮助你更好地理解和解决这类问题。

推荐面试题