九十、動(dòng)態(tài)規(guī)劃系列背包問題之多重背包

「@Author：Runsen」

曾幾何時(shí)，才記得自己還是大一軍訓(xùn)的菜鳥，帶著 迷茫和憧憬踏入大學(xué)，踏入化工學(xué)院，卻踏入這個(gè)行業(yè)，殊不知?dú)q月是最高明的小偷，偷走時(shí)間，帶走青春，一點(diǎn)線索也不留。大學(xué)的玩命學(xué)習(xí)，一轉(zhuǎn)眼，就大四了，一不小心就成了學(xué)校最老的學(xué)長(zhǎng)！

多重背包

前面已經(jīng)介紹完了01背包和完全背包，今天介紹最后一種背包問題——多重背包。

題目是這樣的：來源：https://www.acwing.com/problem/content/4/

有 種物品和一個(gè)容量是 的背包。

第 種物品最多有 件，每件體積是，價(jià)值是 。

求解將哪些物品裝入背包，可使物品體積總和不超過背包容量，且價(jià)值總和最大。輸出最大價(jià)值。

輸入格式 第一行兩個(gè)整數(shù)，，，用空格隔開，分別表示物品種數(shù)和背包容積。

接下來有 行，每行三個(gè)整數(shù) ,,，用空格隔開，分別表示第 種物品的體積、價(jià)值和數(shù)量。

輸出格式 輸出一個(gè)整數(shù)，表示最大價(jià)值。

輸入樣例
4 5
1 2 3 # 體積、價(jià)值和數(shù)量
2 4 1
3 4 3
4 5 2
輸出樣例：
10

狀態(tài)表示：dp[j]

1. 集合：當(dāng)前價(jià)值j的最大值
2. 屬性：最大值

多重背包問題的思路跟完全背包的思路非常類似，只是取值是有限制的，因?yàn)槊考锲返臄?shù)量是有限制的，狀態(tài)轉(zhuǎn)移方程為：dp [j] = max(dp [j], dp [j - k*b] + k*w) 這里的b和w指的是當(dāng)前遍歷的體積和價(jià)值。

這里一維動(dòng)態(tài)規(guī)劃和01背包基一樣，就是多了一個(gè)k的循環(huán)，具體的查看下面代碼。

n, v = map(int, input().split())

dp = [0 for _ in range(v+1)]

for i in range(n):
    b, w, s = map(int, input().split())
    for j in range(v, -1, -1):
        k = 1
        while k <= s and j >= k * b:
            dp [j] = max(dp [j], dp [j - k*b] + k*w)
            k += 1
print(dp[v])

除了上面的方法，還有用最原始的方法，將多個(gè)同一物品轉(zhuǎn)化成不同物品，再用01背包求解

n,v = map(int, input().split())
goods = []
for i in range(n):
    goods.append([int(i) for i in input().split()])

new_goods = []

for i in range(n):
    for j in range(goods[i][2]):
        new_goods.append(goods[i][0:2])

goods = new_goods
n = len(goods)

dp = [0 for i in range(v+1)]

for i in range(n):
 # 01背包倒序
    for j in range(v,-1,-1):
        if j>= goods[i][0]:
            dp[j] = max(dp[j], dp[j - goods[i][0]] + goods[i][1])
print(dp[-1])

關(guān)于多重背包問題中的二進(jìn)制解法，Runsen下一篇再寫。如今就是體現(xiàn)自己的實(shí)力的時(shí)候了。Leetcode刷起來。

Leetcode 面試題 17.16. 按摩師

一個(gè)有名的按摩師會(huì)收到源源不斷的預(yù)約請(qǐng)求，每個(gè)預(yù)約都可以選擇接或不接。在每次預(yù)約服務(wù)之間要有休息時(shí)間，因此她不能接受相鄰的預(yù)約。給定一個(gè)預(yù)約請(qǐng)求序列，替按摩師找到最優(yōu)的預(yù)約集合（總預(yù)約時(shí)間最長(zhǎng)），返回總的分鐘數(shù)。

注意：本題相對(duì)原題稍作改動(dòng)

示例 1：

輸入：[1,2,3,1] 輸出：4 解釋：選擇 1 號(hào)預(yù)約和 3 號(hào)預(yù)約，總時(shí)長(zhǎng) = 1 + 3 = 4。示例 2：

輸入：[2,7,9,3,1] 輸出：12 解釋：選擇 1 號(hào)預(yù)約、 3 號(hào)預(yù)約和 5 號(hào)預(yù)約，總時(shí)長(zhǎng) = 2 + 9 + 1 = 12。

題目，其實(shí)就是不連續(xù)最大子序列。

每個(gè)預(yù)約都可以選擇接或不接來做出思考，每次都有兩種選擇，那么就是狀態(tài)轉(zhuǎn)移方程：

class Solution:
    def massage(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        # 求最值用0 
        dp = [0] * (len(nums))
        dp[0] = nums[0]
        for k in range(1,len(nums)):
            dp[k] = max(dp[k - 1], nums[k] + dp[k - 2])
        return dp[-1]

Leetcode 面試題 08.11. 硬幣

硬幣。給定數(shù)量不限的硬幣，幣值為25分、10分、5分和1分，編寫代碼計(jì)算n分有幾種表示法。(結(jié)果可能會(huì)很大，你需要將結(jié)果模上1000000007)

示例1:

輸入: n = 5 輸出：2 解釋: 有兩種方式可以湊成總金額: 5=5 5=1+1+1+1+1 示例2:

輸入: n = 10 輸出：4 解釋: 有四種方式可以湊成總金額: 10=10 10=5+5 10=5+1+1+1+1+1 10=1+1+1+1+1+1+1+1+1+1

class Solution:
    def waysToChange(self, n: int) -> int:
        # 不就是一個(gè)零錢對(duì)換問題 的完全背包問題? 這里需要將結(jié)果模上 10**9 + 7
        # 求最大值
        dp = [0] * (n+1)
        # f(11) = min(f(10),f(9),f(6)) + 1
        dp[0] = 1
        for i in [1,5,25,10]:
            for j in range(i, n + 1):
                dp[j] += dp[j - i]
        return dp[-1] % 1000000007