多维背包问题matlab实现

以下是多维背包问题的Matlab实现示例：

function [maxValue, x] = multidim_knapsack(n, m, w, p, c)

% n: 物品数量
% m: 背包容量数组
% w: 物品重量数组
% p: 物品价值数组
% c: 物品限制数量数组

% 初始化dp数组
dp = zeros(n+1, sum(m)+1);

% 逐个物品进行决策
for i = 1:n
% 计算物品i的单位价值
unitValue = p(i) ./ w(i);
% 计算物品i的数量上限
maxCount = min(c(i), floor((sum(m) - w(i)) / w(i)));
% 对于每一个数量j，进行决策
for j = 1:maxCount
% 对于每一个体积k，进行决策
for k = sum(m):-1:w(i)
dp(i+1, k) = max(dp(i+1, k), dp(i, k-j*w(i))+j*p(i));
end
end
end

% 根据背包容量数组求解最大价值
maxValue = zeros(size(m));
for i = 1:length(m)
maxValue(i) = max(dp(:,m(i)));
end

% 根据dp数组反推解
x = zeros(n, length(m));
for i = n:-1:1
% 计算物品i的单位价值
unitValue = p(i) ./ w(i);
% 计算物品i的数量上限
maxCount = min(c(i), floor((sum(m) - w(i)) / w(i)));
% 对于每一个数量j，进行决策
for j = maxCount:-1:1
% 对于每一个体积k，进行决策
for k = sum(m):-1:w(i)
if dp(i+1, k) == dp(i, k-j*w(i))+j*p(i)
x(i,:) = x(i,:) + j.*(k >= m);
break;
end
end
end
end

end

调用示例：

% 物品数量
n = 3;
% 背包容量数组
m = [10, 20];
% 物品重量数组
w = [3, 4, 5];
% 物品价值数组
p = [4, 5, 6];
% 物品限制数量数组
c = [2, 1, 1];

[maxValue, x] = multidim_knapsack(n, m, w, p, c);

disp(['最大价值: ', num2str(maxValue)]);
disp('物品选择情况:');
disp(x);