动态规划解0-1背包问题（无价值属性），附Python代码_无价值背包问题py代码

本文解决的问题是【不含有价值属性的】0-1背包问题。具体如下：

现有一个背包体积为V，若干个物品体积为vi。现要求用这些物品把背包装的尽可能满，请问背包最多能装多少体积的物品？（忽略价值属性，只考虑体积）

解题思路是采用动态规划的方式，如下表：

上图假设物品的体积分别为2,3,5,8，背包体积为7。

我们来分析一下动态规划数组代表的含义：第一行代表【只在背包里放第一个物品】，第二行代表【只在背包里放前两个物品】，第n行代表【只在背包里放前n个物品】；第一列代表【背包体积为1时能装的最大体积】，第n列代表【背包体积为n时能装的最大体积】。那么，DP[i][j]的含义就是：在只取前i个物品时，背包容量为j的情况下能装的最大体积。显然，当背包体积为k，物品数量为n时，DP[n][k]即为所求。其时间复杂度为k*n，就一般的无价值背包问题来说这个时间复杂度是完全可以接受的。

动态规划的核心（状态转移函数）：在该问题中，状态转移函数为：

DP[i][j] = max(DP[i-1][j-vi]+vi,DP[i-1][j])，其中vi为第i个物品的体积。

（理解：如果背包装上第i个物品那么装载最大的情况就是当前体积减去vi时装载最大的情况再加上vi；否则就按照前i-1个物体的结果作为当前装载最大的结果。两者中更大的那个就是当前的最大结果。）

这里我们定义DP[ ][x] = -infinity if x < 0 (因为背包体积为负是不合理的，定义为负无穷防止此类情况影响计算）

到此为止无价值属性的0-1背包问题基本解决。附Python代码如下：

# 0-1 bag problem (without value) solution
# use dynamic program method
 
import random
 
 
def DP_01_bag(numlist,target):
    # numlist: int num list
    # target: int num
    DP = [[0 for i in range(target+1)] for i in range(len(numlist))] # initialize
    for i in range(len(numlist)):
        for j in range(target+1):
            if i == 0:
                if j >= numlist[i]:
                    DP[i][j]=numlist[i]
            else:
                if j<numlist[i]:
                    DP[i][j] = DP[i-1][j]
                else:
                    DP[i][j] = max(DP[i-1][j-numlist[i]]+numlist[i],DP[i-1][j])
    return DP[len(numlist)-1][target]
 
if __name__ == "__main__":
    numlist = random.sample(list(range(200)),8)
    target = random.choice(list(range(100,300)))
    result = DP_01_bag(numlist,target)
    print("numlist is :", numlist)
    print("target is :", target)
    print("result is:", result)