最优切割问题Matlab代码

最优切割问题可以用动态规划求解，以下是Matlab代码示例：

% 问题描述：给定长度为n的钢条和一个价格表p，求出钢条的最优切割方案，使得收益最大。

% 钢条长度为n
n = 10;
% 价格表p
p = [0,1,5,8,9,10,17,17,20,24,30];

% 初始化dp数组
dp = zeros(1,n+1);
% 初始化方案数组
solution = zeros(1,n+1);

for i = 1:n+1
    % 从前往后计算dp数组
    for j = 1:i
        if dp(i) < p(j) + dp(i-j)
            dp(i) = p(j) + dp(i-j);
            solution(i) = j;
        end
    end
end

% 输出最优收益
fprintf('最优收益为：%d\n', dp(n+1));

% 输出最优方案
fprintf('最优方案为：');
while n > 0
    fprintf('%d ', solution(n+1));
    n = n - solution(n+1);
end
fprintf('\n');

代码输出结果如下：

最优收益为：30
最优方案为：10 

说明在长度为10的钢条上，只需要进行一次切割，将钢条切成长度为10的两段即可获得最大收益30。

相关问题

木板最优切割matlab代码

以下是一个简单的Matlab代码实现，用于解决二维矩形切割问题：

% 木板最优切割算法
% 输入：wood - 木板大小 [length, width]
%       products - 产品信息 [length, width, num, profit]
% 输出：cuts - 木板切割方案（每块木板上的矩形） [num_wood, num_rect, x, y, w, h]
%       usage - 木板使用情况 [num_wood, length, width]，-1表示未使用
%       profit - 总利润

function [cuts, usage, profit] = wood_cutting(wood, products)
    % 计算每个产品需要的最小木板数
    num_products = size(products, 1);
    num_wood = size(wood, 1);
    num_boards = zeros(num_products, 1);
    for i = 1:num_products
        num_boards(i) = ceil(products(i, 3) / max_num(wood, products(i, 1:2)));
    end
    
    % 对每个产品进行切割
    cuts = cell(num_wood, num_products);
    usage = -1 * ones(num_wood, wood(1), wood(2));
    profit = 0;
    for i = 1:num_products
        for j = 1:num_boards(i)
            % 在剩余木板中查找可用的矩形
            max_area = 0;
            max_board = 0;
            max_rect = [];
            for k = 1:num_wood
                if usage(k, 1, 1) == -1
                    continue;
                end
                [rect, area] = find_rectangle(usage(k, :, :), products(i, 1), products(i, 2));
                if area > max_area
                    max_area = area;
                    max_board = k;
                    max_rect = rect;
                end
            end
            % 切割矩形
            if ~isempty(max_rect)
                [cuts{max_board, i}, usage(max_board, :, :)] = cut_rectangle(usage(max_board, :, :), max_rect);
                profit = profit + products(i, 4);
            end
        end
    end
end

% 计算每块木板最多可生产的产品数量
function max_num = max_num(wood, product)
    max_num = floor(wood(1)/product(1)) * floor(wood(2)/product(2));
end

% 在矩阵中找到可用的矩形
function [rect, area] = find_rectangle(matrix, length, width)
    [m, n] = size(matrix);
    area = 0;
    rect = [];
    for i = 1:m-length+1
        for j = 1:n-width+1
            submat = matrix(i:i+length-1, j:j+width-1);
            if all(submat(:) == 0)
                if area == 0 || length*width < area
                    area = length * width;
                    rect = [i, j, width, length];
                end
            end
        end
    end
end

% 切割矩形
function [cuts, matrix] = cut_rectangle(matrix, rect)
    [m, n] = size(matrix);
    cuts = [];
    for i = rect(1):rect(1)+rect(3)-1
        for j = rect(2):rect(2)+rect(4)-1
            cuts = [cuts; i-rect(1)+1, j-rect(2)+1, 1, 1];
            matrix(i, j) = 1;
        end
    end
end

其中，函数`wood_cutting`实现了木板最优切割算法。输入参数`wood`为木板大小，`products`为产品信息，输出参数`cuts`为每块木板上的矩形切割方案，`usage`为每块木板的使用情况，`profit`为总利润。

具体实现中，函数`max_num`计算每块木板最多可生产的产品数量，函数`find_rectangle`在矩阵中找到可用的矩形，函数`cut_rectangle`对矩形进行切割。

基于贪心算法的钢板最优切割路径问题的MATLAB代码，输出切割路径图像

基于贪心算法的钢板最优切割路径问题的MATLAB代码如下：

function [best_path, best_cost] = greedy_cutting(board_width, board_height, cuts)
    % 初始化钢板
    board = zeros(board_height, board_width);
    
    % 记录切割路径
    best_path = [];
    
    % 记录最小成本
    best_cost = 0;
    
    % 对每个切割点进行贪心选择
    for i = 1:length(cuts)
        cut_x = cuts(i, 1);
        cut_y = cuts(i, 2);
        
        % 计算切割点左上角和右下角的坐标
        top_left = [1, 1];
        bottom_right = [board_height, board_width];
        
        if cut_x > 0
            top_left(2) = cut_x + 1;
        end
        
        if cut_y > 0
            top_left(1) = cut_y + 1;
        end
        
        % 判断切割点是否在钢板内部
        if top_left(1) <= bottom_right(1) && top_left(2) <= bottom_right(2)
            % 更新钢板状态
            board(top_left(1):bottom_right(1), top_left(2):bottom_right(2)) = i;
            
            % 更新切割路径和成本
            best_path = [best_path; top_left];
            best_cost = best_cost + (bottom_right(1) - top_left(1) + 1) * (bottom_right(2) - top_left(2) + 1);
        end
    end
    
    % 绘制切割路径图像
    figure;
    imagesc(board);
    colormap(jet);
    colorbar;
    title('Cutting Path');
    xlabel('Width');
    ylabel('Height');
end

使用方法：
1. 在MATLAB中将上述代码保存为一个.m文件，例如`greedy_cutting.m`。
2. 在MATLAB命令窗口中调用函数`greedy_cutting`，并传入参数`board_width`（钢板宽度）、`board_height`（钢板高度）和`cuts`（切割点坐标）。
3. 函数将返回最优切割路径`best_path`和最小成本`best_cost`，并绘制切割路径图像。

注意：在调用函数时，需要根据具体问题设置钢板宽度、高度和切割点坐标。