Skip to content

Latest commit

 

History

History
187 lines (156 loc) · 7.72 KB

1.3背包问题.md

File metadata and controls

187 lines (156 loc) · 7.72 KB

动态规划 之 背包问题

  • 01背包

    • 有N件物品，背包的最大承重为M，每件物品的数量均为1，价值集合为V，重量集合为W，计算该背包可以承载的物品的最大价值。

    动态规划思想

    • 状态

      当前背包还可以承受的最大重量，当然初始状态就是M；

    • 子问题

      对于某件物品i而言，子问题可理解为选择这件物品，或者是不选择这件物品。

    • 状态转移方程

    其中表示背包已装物品重量为M时的最大价值，上述比较的两者，前者表示不装第i件物品时，背包已经承载物品的最大价值，后者表示装了第i件物品后，剩余的空间可以装载物品的最大价值与第i件物品价值的和。两者取最大，则可保证最后的方案是最优的。

    解题思路图示： image

    基于Python3的代码

weight = [4, 3, 2, 6, 5]
value = [3, 4, 6, 7, 9]
maxweight = 8
# 只输出最大价值
def ZeroOnePack_Simple(W, V, MW):  # 0-1背包
   # 存储最大价值的一维数组
   valuelist = [0] * (MW + 1)
   # 开始计算
   for ii in range(len(W)):  # 从第一个物品
       copyvalue = valuelist.copy()
       for jj in range(MW + 1):  # 从重量0
           if jj >= W[ii]:  # 如果重量大于物品重量
               copyvalue[jj] = max(valuelist[jj - W[ii]] + V[ii], valuelist[jj])  # 选中第ii个物品和不选中，取大的
       valuelist = copyvalue.copy()  # 更新
   return '最大价值：', valuelist[-1]

#  也输出选择物品的编号
def ZeroOnePack(W, V, MW):  # 0-1背包
   # 存储最大价值的一维数组
   valuelist = [0] * (MW + 1)
   # 存储物品编号的字典
   codedict = {i: [] for i in range(0, MW + 1)}
   # 开始计算
   for ii in range(len(W)):  # 从第一个物品
       copyvalue = valuelist.copy()
       copydict = codedict.copy()
       for jj in range(MW + 1):  # 从重量0
           if jj >= W[ii]:  # 如果重量大于物品重量
               copyvalue[jj] = max(valuelist[jj - W[ii]] + V[ii], valuelist[jj])  # 选中第ii个物品和不选中，取大的
               # 输出被选中的物品编号
               if copyvalue[jj] > valuelist[jj]:
                   copydict[jj] = [ii]
                   for hh in codedict[jj - W[ii]]:
                       copydict[jj].append(hh)
       codedict = copydict.copy()  # 更新
       valuelist = copyvalue.copy()  # 更新
   print('所需物品：', sorted([1 + code for code in codedict[MW]]))
   return '最大价值：', valuelist[-1]

print(ZeroOnePack_Simple(weight, value, maxweight))

  • 完全背包

    • 有N件物品，背包的最大承重为M，每件物品的数量无限，价值集合为V，重量集合为W，计算该背包可以承载的物品的最大价值。

    这个和0-1背包的最大区别在于：每计算一次V值，就立即更新。其状态转移方程和0-1背包相同，因为有实时的更新V值，就相当于同一个物品可以多次选取。

下面给出基于Python3的代码

weight = [4, 3, 2, 6, 5]
value = [3, 4, 6, 7, 9]
maxweight = 8

# 只输出最大价值
def CompletePack_Simple(W, V, MW):#完全背包
    #存储最大价值的一维数组
    valuelist = [0] * (MW + 1)
    #开始计算
    for ii in range(len(W)):#从第一个物品
        for jj in range(MW + 1):#从重量0
            if jj >= W[ii]:#如果重量大于物品重量
                valuelist[jj] = max(valuelist[jj - W[ii]] + V[ii], valuelist[jj])#选中第ii个物品和不选中，取大的
    return '最大价值：', valuelist[-1]

#  也输出选择物品的编号以及个数
def CompletePack(W, V, MW):#完全背包
    #存储最大价值的一维数组
    valuelist = [0] * (MW + 1)
    #存储物品编号的字典
    codedict = {i: [] for i in range(0, MW + 1)}
    #开始计算
    for ii in range(len(W)):#从第一个物品
        copyvalue = valuelist.copy()
        copydict = codedict.copy()
        for jj in range(MW + 1):#从重量0
            if jj >= W[ii]:#如果重量大于物品重量
                cc = copyvalue[jj]
                copyvalue[jj] = max(copyvalue[jj - W[ii]] + V[ii], copyvalue[jj])#选中第ii个物品和不选中，取大的
                #输出被选中的物品编号
                if copyvalue[jj] > cc:
                    copydict[jj] = [ii]
                    for hh in copydict[jj - W[ii]]:
                        copydict[jj].append(hh)
        codedict = copydict.copy()#更新
        valuelist = copyvalue.copy()#更新
    result = ''
    for hcode in sorted(list(set(copydict[MW]))):
        result += '物品：%d :%d个' % (hcode + 1, copydict[MW].count(hcode))
    print(result)
    return '最大价值：', valuelist[-1]

print(CompletePack_Simple(weight, value, maxweight))

  • 多重背包

    • 有N件物品，背包的最大承重为M，每件物品的数量集合为C，价值集合为V，重量集合为W，计算该背包可以承载的物品的最大价值。

这个和完全背包的最大区别在于：完全背包因为没有物品数量的限制，因此可以无限叠加。因此需要加上对数量的限制语句。

下面是基于Python3的代码

weight = [4, 3, 2, 6, 5]
value = [3, 4, 6, 7, 9]
count = [3, 2, 1, 1, 0]
maxweight = 8

#  只输出最大价值
def MultiplePack_Simple(W, V, C, MW):  # 多重背包
    # 存储最大价值的一维数组
    valuelist = [0] * (MW + 1)
    # 开始计算
    for ii in range(len(W)):  # 从第一个物品
        copyvalue = valuelist.copy()
        for jj in range(MW + 1):  # 从重量0
            if jj >= W[ii]:  # 如果重量大于物品重量
                for gg in range(C[ii] + 1):  # 限制=数量
                    if gg * W[ii] <= jj:
                        copyvalue[jj] = max(valuelist[jj - gg * W[ii]] + gg * V[ii], copyvalue[jj])
        valuelist = copyvalue.copy()  # 更新
    return '最大价值：', valuelist[-1]

#  也输出编号以及个数
def MultiplePack(W, V, C, MW):  # 多重背包
    # 存储最大价值的一维数组
    valuelist = [0] * (MW + 1)
    # 存储物品编号的字典
    codedict = {i: [] for i in range(0, MW + 1)}
    # 开始计算
    for ii in range(len(W)):  # 从第一个物品
        copyvalue = valuelist.copy()
        copydict = codedict.copy()
        # 存储物品所用数量的一维数组
        number = [0] * (MW + 1)
        for jj in range(MW + 1):  # 从重量0
            if jj >= W[ii]:  # 如果重量大于物品重量
                for gg in range(C[ii] + 1):  # 限制数量
                    cc = copyvalue[jj]
                    if gg * W[ii] <= jj:
                        copyvalue[jj] = max(valuelist[jj - gg * W[ii]] + gg * V[ii], copyvalue[jj])
                        if copyvalue[jj] > cc:
                            number[jj] += 1
                            copydict[jj] = number[jj] * [ii]
                            for hh in codedict[jj - number[jj] * W[ii]]:
                                copydict[jj].append(hh)
        codedict = copydict.copy()  # 更新
        valuelist = copyvalue.copy()  # 更新
    result = ''
    for hcode in sorted(list(set(copydict[MW]))):
        result += '物品：%d: %d个。' % (hcode + 1, copydict[MW].count(hcode))
    print(result)
    return '最大价值：', valuelist[-1]


print(MultiplePack_Simple(weight, value, count, maxweight))