赞
踩
有10件货物要从甲地运送到乙地,每件货物的重量(单位:吨)和利润(单位:元)如下表所示:
由于只有一辆最大载重为30t的货车能用来运送货物,所以只能选择部分货物配送,要求确定运送哪些货物,使得运送这些货物的总利润最大。
原问题: 在满足重量约束的条件下,将这m件物品选择性的放入容量为W的背包中所能获得的最大利润.
子问题: 在满足重量约束的条件下,将前i (i <=m) 件物品选择性的放入容量为 (j<=W) 的背包中所能获得的最大利润.
其实这个问题我们可以采用自上而下的迭代,创建一个长为容量,宽为数量的二维矩阵,从第一行开始,第一行代表第一个物品,从左到右重量够的取最优解,然后开始第二行,即第二个物品,此时最优解涉及到第一个,可参考上一行的最优解,同第二个物品比较,得出两个物品的最优解…以此类推
我们现在来看一个例子
由于我们创建的那个表格是 物品和容量,所以先选出最后一列中取出最大的,然后回到上面的表,减去对应的物品编号,得出上一个物品,得出剩余的背包空间,以此类推,很像礼物问题的求出礼物编号
import numpy as np class solution(): def __init__(self): self.profile= [11,12,10,26,14,16] self.weight = [3, 2 ,2, 5, 1, 3] self.W=10 def total(self): ind=0 num = len(self.profile) DP = np.zeros((num,self.W)) #第一行 if self.weight[0] < self.W : DP[0,(self.weight[0]-1):(self.W)]=self.profile[0] #第一列 for i in range(1,num): for each in self.weight[0:i]: if each ==1: IND=self.weight.index(1) DP[i-1:num,0]=self.profile[IND] ind=1 break if ind==0: DP[i,0]=0 for i in range(1,num): for j in range(1,self.W): if self.weight[i] > j+1: DP[i,j]= DP[i-1,j] elif self.weight[i] == j+1: DP[i,j]=max(DP[i-1,j],self.profile[i]) else: DP[i,j]=max(DP[i-1,j],self.profile[i]+DP[i-1,j-self.weight[i]]) return DP def Object(self,DP): if len(DP)>0: Object_num=[] num = len(self.profile) ww=self.W tmp=list(DP[0:num,self.W-1]) while 1: ind=tmp.index(max(tmp)) ww=ww-self.weight[ind] Object_num.append(ind+1) if ((ind>1) ==True) and ((ww>0) ==True): tmp=list(DP[0:ind,ww-1]) else: break result=Object_num.sort() else: return -1 return result backpack=solution() DP=backpack.total() print(DP) Object_num=backpack.Object(DP) print(Object_num)
p = [540,200,180,350,60,150,280,450,320,120]; %利润 w = [6 ,3, 4 ,5, 1, 2, 3, 5, 4, 2]; %重量 W = 30; %容量 f = knapsack01problem1(p,w,W) function [f, IND] = knapsack01problem2(p,w,W) % 输入: p:物品的利润 w:物品的重量 W:背包的容量 % 为了编程方便,假设W是大于等于2的正整数;w中每个元素都是大于等于1的正整数 m = length(p); % 物品个数 FF = zeros(m,W); % 初始化DP数组 % FF(i,j):前i件物品选择性的放入容量为j的背包中所能获得的最大利润 if w(1) <= W % 初始化第一行 FF(1,w(1):end) = p(1); end for i = 2:m % 初始化第一列 FF(i,1) = max([p(w(1:i) == 1),0]); end % i,j>1的情况 for i = 2:m for j = 2:W if w(i) > j % 第i件物品的重量w(i)比背包的容量j还要大 FF(i,j) = FF(i-1,j) ; elseif w(i) == j % 第i件物品的重量w(i)等于背包的容量j FF(i,j) = max(FF(i-1,j), p(i)); % 不放进去和放进去取较大的值 else % 第i件物品的重量w(i)小于背包的容量j FF(i,j) = max(FF(i-1,j), p(i)+FF(i-1,j-w(i))); % 不放进去和放进去取较大的值 end end end f = FF(m,W); IND = []; % 选择的物品编号IND初始化为空 if f > 0 % 只要有利润,就可以利用FF来计算选择的物品编号IND ww = W; % 初始化背包的剩余容量为整个背包的容量W tmp = FF(:,ww); % 取出最后一列 while 1 % 不断循环下去,后面通过条件判断来退出循环 ind = find(tmp == max(tmp),1) ; % 找到装入背包的那个物品 ww = ww - w(ind); % 更新背包的剩余容量 IND = [IND,ind]; % 更新IND里面的元素 if ind > 1 && ww>0 % 只要不是第一个物品或者背包容量为空 tmp = FF(1:ind-1,ww); % 重新取出剩余容量的那一列(只保留前面的物品) else break % 跳出循环 end end IND = sort(IND); % 排序下,输出好看点 end end
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。