背包问题动态规划matlab,算法问题(二)–动态规划之01背包问题

好的，关于背包问题的动态规划算法，我可以为您提供以下 Matlab 代码：

% 01背包问题
% 输入：重量数组w，价值数组v，背包容量C
% 输出：最大价值maxValue，选择物品数组x
function [maxValue, x] = knapsack01(w, v, C)
n = length(w);
% dp数组，dp(i,j)表示前i个物品，容量为j时的最大价值
dp = zeros(n+1, C+1);
% 记录选择的物品
x = zeros(1, n);
% 动态规划
for i = 1:n
    for j = 1:C
        if j < w(i)
            % 背包容量不足，不能选择第i个物品
            dp(i+1, j) = dp(i, j);
        else
            % 可以选择第i个物品，取最大价值
            dp(i+1, j) = max(dp(i, j), dp(i, j-w(i))+v(i));
        end
    end
end
% 回溯求解选择的物品
j = C;
for i = n:-1:1
    if dp(i+1, j) > dp(i, j)
        x(i) = 1;
        j = j - w(i);
    end
end
maxValue = dp(n+1, C);
end

使用方法：

- 输入重量数组 `w`，价值数组 `v` 和背包容量 `C`
- 输出最大价值 `maxValue` 和选择物品数组 `x`，其中 `x(i)` 为 1 表示选择第i个物品，为 0 表示不选择。

示例：

w = [2, 3, 4, 5];
v = [3, 4, 5, 6];
C = 8;
[maxValue, x] = knapsack01(w, v, C);
disp(['最大价值为：', num2str(maxValue)]);
disp(['选择的物品为：', num2str(x)]);

输出：

最大价值为：11
选择的物品为：1 1 1 0

其中，选择的物品为前三个物品，总重量为 2+3+4=9，总价值为 3+4+5=12。