动态规划matlab编写代码

动态规划是一种解决最优化问题的有效算法，以下是一个使用Matlab实现动态规划的示例代码：

function [max_value, opt_path] = dynamic_programming(c, w, W)
% c: cost vector
% w: weight vector
% W: capacity
% max_value: maximum value
% opt_path: optimal path

n = length(c); % number of items

% initialization 
f = zeros(n+1, W+1); % f(i, j) represents the maximum value of the first i items with capacity j
for j = 1:W+1
    f(1, j) = 0;
end

% dynamic programming
for i = 2:n+1
    for j = 1:W+1
        if j < w(i-1) % can not add the i-th item
            f(i, j) = f(i-1, j);
        else % choose whether to add the i-th item or not
            f(i, j) = max(f(i-1, j), f(i-1, j-w(i-1))+c(i-1));
        end
    end
end

max_value = f(n+1, W+1); % maximum value
opt_path = zeros(1, n); % optimal path
j = W+1;
for i = n:-1:1
    if f(i+1, j) == f(i, j) % the i-th item is not added
        opt_path(i) = 0;
    else % the i-th item is added
        opt_path(i) = 1;
        j = j - w(i);
    end
end
end

该函数接受三个输入参数：c是每个物品的价值，w是每个物品的重量，W是背包的最大容量。它返回两个输出参数：max_value是背包能装下的最大价值，opt_path是一个二进制数组，表示哪些物品被选择放入背包中。

该函数使用一个二维数组f来存储子问题的解，其中f(i,j)表示前i个物品中，容量为j的背包所能容纳的最大价值。在动态规划的过程中，根据当前物品的重量和价值，决定是否将其放入背包中。

最后，通过回溯法可以得到选择哪些物品可以达到最大价值。