云博
0-1背包问题的解法(动态规划)

阅读量:(73) 您现在所在的位置: 首页 百宝箱 Leetcode 0-1背包问题的解法(动态规划) 作者:慎独、
简介:0-1背包问题的解法(动态规划)

0-1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi

问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?

假设:

n = 5

w = [2,5,1,3,6]

v = [2,4,5,2,3]

c = 9

按照动态规划的五大步骤进行分析:

① 状态定义:要计算背包物品的总价值,我们可以设定一个空间来存储该总价值

② 状态转移方程:建模,创建一个二维数组dp[i][j],来表示第i个物品,背包容量为j的时候时候的最大价值。

③ 初始化值:默认我们将dp整个数组初始化为0,同时给w和v添加边界条件0,使得w = [0,2,5,1,3,6], v = [0,2,4,5,2,3],那么为什么要这样做呢?

我们尝试分情况讨论一下:

(1)当 j<w[i],此时表示第i个物品的重量大于总背包容量,那么此时是无法装进该物品的。因此方程:dp[i][j]=dp[i-1][j]

(2)当j>=w[i],此时表示第i个物品的重量小于等于总背包量,这时候就需要根据最优性质原理,方程:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]) 因为当前物品的总价值,可能决定于前一个物品的总价值大,也可能决定于加上这个物品后得到的总价值。

(3)我们要从第i=1开始,所以需要添加一个边界0,防止越出异常。

④ 选取结果,选取dp[-1][-1]

代码:

def one_two_bags():
    n,w,v,c = 5,[2,5,1,3,6],[2,4,5,2,3],9
    m = len(w)
    dp = [[0 for _ in range(m)] for _ in range(m)]
    for i in range(1,m):
       for j in range(1,c):
          if j<w[i]:
             dp[i][j] = dp[i-1][j]
          else:
             dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
    return dp[-1][-1]

注:j从1开始,从0开始没有意义,因为初始化dp全为0,减小了m次循环的时间复杂度。

点赞一波

1

    欢迎您游客

 小云标签


 网站统计:


笔记数: 总点赞量:

总访问量:   分类数目:

服务器:阿里云服务器

 网站动态: