動态規劃 背包/金礦問題

1. 題目描述

國王發現五個金礦，其中金礦的情況如下：

含金量分别為： 400、500、200、300、350

所需人數為： 5、5、3、4、3

現在總的人力為10，求能獲得最大金币數

2. 解題思路

動态規劃核心思路無非兩點：終止（邊界）條件 + （讨論條件）狀态轉移

假設金礦的含量為g [] 需要的人數為 p[] 總的人數為m

對每一所礦，這裡假定第i所礦。需要的人數為p[i]，含金量為g[i]。 讨論如下：

• p[i] > m 【人手不夠】狀态轉移方程為 F(g[i+1:], p[i+1:], m)
• p[i] <= m 狀态轉移方程為 max (F(g[i+1:], p[i+1:], m-p[i]) + g[i], F(g[i+1:], p[i+1:], m))
• 終止條件： g為空或者m為0 傳回0

3. AC代碼

• 簡單遞歸

  def get_most_gold(g: list, p: list, m):
      if not g or m == 0:
          return 0
      else:
          if p[0] > m:
              return get_most_gold(g[1:], p[1:], m)
          else:
              return max(get_most_gold(g[1:], p[1:], m), get_most_gold(g[1:], p[1:], m-p[0]) + g[0])
             

• 動态規劃清單記錄

  為了友善了解這裡的邏輯，采用表格去模拟思路：

  行代表第幾所金礦，列代表人數

  1	2	3	4	5	6	7	8	9	10
  第一所金礦	400	400	400	400	400	400
  第二所金礦
  第三所金礦
  第四所金礦
  第五所金礦

  在第一所金礦需要人數為5人，由于1-4人時勞動力不足，結果為0；當人數超過5人時，由于選擇隻有這一所金礦，是以結果為400。

  類似的，面對第二所金礦時，結果如下：

  1	2	3	4	5	6	7	8	9	10
  第一所金礦	400	400	400	400	400	400
  第二所金礦	500	500	500	500	500	900
  第三所金礦
  第四所金礦
  第五所金礦

  當人數為5人時，結果為500。但人數為10人時，除了采集第二所金礦，還可以采集第一所，是以結果為900。

  考慮第三、四、五所金礦：

  1	2	3	4	5	6	7	8	9	10
  第一所金礦	400	400	400	400	400	400
  第二所金礦	500	500	500	500	500	900
  第三所金礦	200	200	500	500	500	700	700	900
  第四所金礦	200	300	500	500	500	700	800	900
  第五所金礦	350	350	500	550	650	850	850	900

  觀察每一行，結果都可以由上一行和目前金礦的狀态去确定。

  如上表中标黑的第五行第八列。可以這麼了解：目前的人數為8人，大于第五所金礦所需的3人，剩餘勞動力為5人，則取值為 上一個狀态8個勞動力的最大值700 或者開采目前金礦花費3人得到350，和剩餘勞動力5人在上一個狀态能得到的最大值500之和，即max（700, 350+500）。

  def get_most_gold_2(g: list, p: list, m):
      # 初始化邊界
      pre_res = [0 if p[0] > i else g[0] for i in range(0, m+1)]
      res = [0 for i in pre_res]
  
      # 狀态轉移
      for i in range(1, len(g)):
          for j in range(0, m+1):
              if p[i] > j:
                  res[j] = pre_res[j]  # 當所需人數大于目前人數  目前能得到最大值和上一個狀态一樣
              else:
                  res[j] = max(g[i] + pre_res[j-p[i]], pre_res[j])   # 當所需人數小于目前人數  取兩種情況中的最大值
  
          pre_res = [i for i in res] # 更新前一行的元素
  
      return pre_res[m]
             

• 分析：

  遞歸的解法簡單暴力，但是時間複雜度為O(2^n)；使用清單記錄每行動态規劃的結果，時間複雜度為O(mn)。