动态规划0-1背包问题python版本

  动态规划就是将问题划分为子问题，通过子问题的最优解得到原问题的最优解。动态规划把每个求解过程的子问题记录下来，下次碰到同样的子问题可以直接使用之前的结果。下面学习一类经典的背包问题。

1.背包问题

问题是这样的：n 件物品，每个重量 w[i]，价值 c[i] 。背包容量 V。问如何使得背包内物品总价值最大。每种物品只有一件。

定义 dp[i][j] 表示前 i 件物品装入容量 j 的背包的价值，那么：

1.  
   dp[i][j] = Math.max(
2.  
   dp[i-1][j], // 不放第 i 件物品
3.  
   dp[i-1][j-w[i]] c[i] // 放第 i 件物品
4.  
   )

因此代码如下：

1.  
   for (int i = 0; i < n; i ) {
2.  
   for (int j = w[i]; j <= V; j ) {
3.  
   dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] c[i]);
4.  
   }
5.  
   }

1. 整体代码如下

1.  
   """
2.  
   N=4,V=10
3.  
   w1 = 8, c1 = 9
4.  
   w2 = 3, c2 = 3
5.  
   w3 = 4, c3 = 4
6.  
   w4 = 3, c4 = 3
7.  
    
8.  
   通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，
9.  
   用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。
10.  
     
11.  
    定义dp[i][j]为前i件物品装入容量为j的的背包的价值,即每放进一个物品就要
12.  
    牺牲背包二点容量来获取背包的总价值
13.  
    """
14.  
    import numpy as np
15.  
    c=[0,9,3,4,3]
16.  
    w=[0,8,3,4,3]
17.  
    N=4
18.  
    V=10
19.  
     
20.  
    def 背包问题(N,w,c,V):
21.  
    #既然是将物品放到背包，那么是以物品为主题，首先进行第一层循环,用w[i]可以遍历上一层的每一个商品的重量
22.  
    dp = np.zeros((N 1, V 1), dtype=np.int32)
23.  
    for i in range(1,N 1,1):
24.  
    #然后再来第二层循环，j表示容量，j的最大值为容量V,最小值为必须大于当前遍历的物品的重量
25.  
    for j in range(1,V 1,1): #这里出现一个问题：为什么每次要递减一，因为重量的最小单位就是1呀哈哈
26.  
    if(j<w[i]):
27.  
    dp[i,j]=dp[i-1,j] #如果说当前要装入的物品的重量大于背包的容量，直接返回未装之前背包的价值
28.  
    else: #否则，我们挑选最大值未转这个物品之前背包的价值 和 装了之后背包的价值
29.  
    dp[i,j]=max(dp[i-1,j],dp[i-1,j-w[i]] c[i])
30.  
    return dp
31.  
     
32.  
    a=背包问题(N,w,c,V)
33.  
    print(a)

2.复盘

在初始化一个dp二位数组的时候，应该注意到创建数组有三种办法

1.

1.  
   a=[[]*11]*5
2.  
   a[0].append(1)
3.  
   print(a)

2.

1.  
   b=[[] for j in range(5)]
2.  
   for j in range(11):
3.  
   b[0].append(0)
4.  
   for j in range(5):
5.  
   b[j].append(0)
6.  
   print(b)

3. 用numpy包创建二维数组，这里推荐用numpy，因为其本身就是用来做矩阵运算的

一共两个参数：前面的行列的维度，后面的是数据类型

1.  
   import numpy as np
2.  
   dp=np.zeros((N 1,V 1),dtype=int32)

        在创建代码的过程中，我一开始用的是第一种办法初始化矩阵，后来发现结果总是有问题，其他行的值会与第一行的值相等，最后查阅资料才发现  a=[[]*11]*5，a = [[b]]*3只是创建了3个指向b的应用，所以一旦b改变，a中的3个列表也会改变。 所以在选择初始化二维矩阵的时候。优先选择用numpy创建，这算是个人踩过的一个坑，希望后面的人不要犯同样的小错误。

经过运算之后，结果如下

 最后我将运算得到的二维数组转化为DateFrame,之后保存至excel，关于这个pd.ExcelWrite的格式如下，（已经存在的地址，模型=追加，引擎=openyxl,......）

1.  
   import pandas as pd
2.  
   df=pd.DataFrame(a)
3.  
    
4.  
   with pd.ExcelWriter('T:/Desktop/表.xlsx', mode='a', engine='openpyxl') as writer:
5.  
   df.to_excel(writer, sheet_name="动态规划")

这篇好文章是转载于：学新通技术网