01背包问题matlab

01背包问题是一个经典的动态规划问题，在MATLAB中可以使用以下代码实现：

function [max_value, best_items] = knapsack_01(weights, values, capacity)
% weights: 物品的重量数组
% values: 物品的价值数组
% capacity: 背包的容量
% max_value: 背包能够装下的最大价值
% best_items: 最优解对应的物品选择情况

n = length(weights); % 物品数量
f = zeros(n+1, capacity+1); % 初始化dp数组
for i = 1:n
    for j = 1:capacity+1
        if weights(i) > j-1
            f(i+1,j) = f(i,j); % 物品i不能放进背包中
        else
            % 物品i可以放进背包中，需要比较放与不放哪种情况更优
            f(i+1,j) = max(f(i,j), f(i,j-weights(i))+values(i));
        end
    end
end

max_value = f(n+1, capacity+1); % 背包能够装下的最大价值

% 查找最优解对应的物品选择情况
best_items = zeros(1, n);
j = capacity+1;
for i = n:-1:1
    if f(i+1,j) > f(i,j)
        best_items(i) = 1;
        j = j - weights(i);
    end
end
end

其中，`weights`和`values`分别为物品的重量和价值数组，`capacity`为背包的容量。函数返回值为背包能够装下的最大价值以及最优解对应的物品选择情况。

使用示例：

weights = [2, 3, 4, 5];
values = [3, 4, 5, 6];
capacity = 8;
[max_value, best_items] = knapsack_01(weights, values, capacity);
disp(max_value);
disp(best_items);

输出结果：

9
     0     0     1     1