beibao.m

1.1 背包问题 有一个徒步旅行者

function [value]=MyFirstDP2
%动态规划模型求解程序示例
%以【背包问题】为例（一维背包问题）
% P212~215，《组合数学》（修订本）孙世新，电子科技大学出版社
global M    %M矩阵第i列针对第i种货物的信息
M=[3 4 5;   %第一行：单位重量
   4 5 6];  %第二行：单位价值
value = getmaxvalue(3,10);
%下面是一个子函数（属于递归函数）
function value=getmaxvalue(k,y)
global M
value = -inf;
if k==1 
   value = M(2,1)*fix(y/M(1,1));%对第一阶段（只包含第一个决策变量）
   which = fix(y/M(1,1));
   disp(sprintf('第%d阶段f%d(%8.2f)=%8.2f=%d(单)*%d(决策)',k,k,y,value,M(2,k),which))
   return
end
for num=0 : fix(y/M(1,k))
   curvalue=M(2,k)*num + getmaxvalue(k-1,y-M(1,k)*num);
   if curvalue > value 
      value = curvalue;
      which=num;%存储第 k阶段的决策变量最优值
   end %if   
end %for
disp(sprintf('第%d阶段f%d(%8.2f)=%8.2f=%d(单)*%d(决策)+f(%d,%8.2f)',...
k,k,y,value,M(2,k),which,k-1,y-M(1,k)*which))