动态规划（五）

01背包问题 ( 01 Knapsack problem)

有10件货物要从甲地运送到乙地,每件货物的重量(单位:吨)和利润(单位:元)如下表所示:

由于只有一辆最大载重为30t的货车能用来运送货物,所以只能选择部分货物配送,要求确定运送哪些货物,使得运送这些货物的总利润最大。

1.1 原问题和子问题

原问题: 在满足重量约束的条件下,将这m件物品选择性的放入容量为W的背包中所能获得的最大利润.

子问题: 在满足重量约束的条件下,将前i (i <=m) 件物品选择性的放入容量为 (j<=W) 的背包中所能获得的最大利润.

其实这个问题我们可以采用自上而下的迭代，创建一个长为容量，宽为数量的二维矩阵，从第一行开始，第一行代表第一个物品，从左到右重量够的取最优解，然后开始第二行，即第二个物品，此时最优解涉及到第一个，可参考上一行的最优解，同第二个物品比较，得出两个物品的最优解…以此类推

1.2 寻找物品编号

我们现在来看一个例子

由于我们创建的那个表格是 物品和容量，所以先选出最后一列中取出最大的，然后回到上面的表，减去对应的物品编号，得出上一个物品，得出剩余的背包空间，以此类推，很像礼物问题的求出礼物编号

python 解法

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)

matlab 解法

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