背包问题最小价值matlab

以下是使用Matlab解决背包问题的最小价值实现示例：

% 背包容量
W = 10;

% 物品重量
weights = [2, 3, 4, 5];

% 物品价值
values = [3, 4, 5, 6];

% 物品数量
n = length(weights);

% 创建一个n+1行，W+1列的矩阵，用于存储最小价值
min_values = zeros(n+1, W+1);

% 初始化第一行为0
min_values(1,:) = 0;

% 开始填充矩阵
for i = 2:n+1
    for j = 1:W+1
        % 如果当前物品重量小于等于背包容量，则可以考虑将其放入背包中
        if weights(i-1) <= j
            % 计算当前物品放入背包后的价值
            value_with_current_item = values(i-1) + min_values(i-1, j-weights(i-1));
            % 计算当前物品不放入背包的价值
            value_without_current_item = min_values(i-1, j);
            % 取两者中的最小值，更新最小价值矩阵
            min_values(i,j) = min(value_with_current_item, value_without_current_item);
        else
            % 如果当前物品重量大于背包容量，则不能将其放入背包中，直接取上一行的价值
            min_values(i,j) = min_values(i-1,j);
        end
    end
end

% 输出结果
fprintf("背包容量为 %d 时的最小价值为 %d\n", W, min_values(n+1,W+1));

注：该实现使用动态规划方法，时间复杂度为O(nW)，其中n为物品数量，W为背包容量。