分组背包问题Matlab实现??之基本背包问题

发布于:2021-07-20 04:26:06

2016年7月27日星期三


T.s.road总结笔记:分组背包问题Matlab实现??之基本背包问题


项目源码:https://github.com/Tsroad/KnapsackProblemSeries




作者说明:


When running thisprogramme, the author’s PCsetting is:


Microsoft Windows 7 (SP1) + Matlab R2010b +CPUi5-4590 + RAM 4.0GB.


?(LabSX309; Check by Keung Charteris or T.s.road CZQ & F.Hong)


题目


有N件物品和一个容量为C的背包。第i件物品的价值是V[i],重量是W[i]。求解将哪些物品装入背包,使得重量总和不超过背包容量,且价值总和最大。


?


基本思路


这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。其状态转移方程便是:


M(i,v)=max{第i件物品不放入背包, 第i件物品放入背包}


M(i,v)=max{M( i-1 , C) , M( i-1 , C-W(i) ) + V(i)}


用子问题定义状态:即M(i,v)表示前i件物品恰放入一个容量为C的背包可以获得的最大价值。


M(i,v)=max{(不放入物品i)将前i-1件物品放入容量为C的背包中的最大价值,


(放入物品i)将前i-1件物品放入容量为C- W(i)的背包中的最大价值+ V(i)}


?


这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为C的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为C的背包中”;如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为C-W(i)的背包中”,此时能获得的最大价值就是M( i-1 , C-W(i) )再加上通过放入第i件物品获得的价值V(i)。



% 问题分析
% 1. 判断第一个物品放或不放;
% 2. 判断下一个物品是放还是不放;M[i,c]=M[i-1,c] or M[i,c]= M[i-1,c-w(i)]+v(i);
% 3. 重复2;
% 4. 找出这些物品。


clc; %清除所有
clear all;%清除变量
close all;%关闭图片

Capacity=10;% 背包的容量
Weight= [0,2,2,6,5,4];% 物品的重量,其中0号位置不使用 。
Value= [0,6,3,5,4,6];% 物品对应的价钱,0号位置置为空。
NumberOfObject =length(Weight);% n为物品的个数
TransferMatrix=[];%定义状态转移矩阵
ObjectState=[];%背包里物品的状态

%1.判断第一个物品放或不放;
for FlagTemp=1:11
if Weight(NumberOfObject) TransferMatrix(NumberOfObject,FlagTemp)=Value(NumberOfObject) ;
else
TransferMatrix(NumberOfObject,FlagTemp)=0;
end
end

%2.判断下一个物品是放还是不放;不放时:F[i,v]=F[i-1,v];放时:F[i,v]=max{F[i-1,v],F[i-1,v-C_i]+w_i};
%3.重复2.
for FlagTempExternal=NumberOfObject-1:-1:1
for FlagTemp=1:11
if FlagTemp<=Weight(FlagTempExternal)
TransferMatrix(FlagTempExternal,FlagTemp)=TransferMatrix(FlagTempExternal+1,FlagTemp);
else
if TransferMatrix(FlagTempExternal+1,FlagTemp)>TransferMatrix(FlagTempExternal+1,FlagTemp-Weight(FlagTempExternal))+Value(FlagTempExternal)
TransferMatrix(FlagTempExternal,FlagTemp)=TransferMatrix(FlagTempExternal+1,FlagTemp);
else
TransferMatrix(FlagTempExternal,FlagTemp)=TransferMatrix(FlagTempExternal+1,FlagTemp-Weight(FlagTempExternal))+Value(FlagTempExternal);
end
end
end
end
TransferMatrix

%4.找出这些物品。

FlagTempExternal=Capacity;
for FlagTemp=1:NumberOfObject-1
if TransferMatrix(FlagTemp,FlagTempExternal)==TransferMatrix(FlagTemp+1,FlagTempExternal)
ObjectState(FlagTemp)=0;
else
ObjectState(FlagTemp)=1;
FlagTempExternal=FlagTempExternal-Weight(FlagTemp);
end
end
if TransferMatrix(NumberOfObject,FlagTempExternal)==0
ObjectState(NumberOfObject)=0;
else
ObjectState(NumberOfObject)=1;

end

ObjectState


运行结果:







?

相关推荐

最新更新

猜你喜欢