題目出處

440 · Backpack III

難度

medium

個人範例程式碼

from typing import (
    List,
)

class Solution:
    """
    @param a: an integer array
    @param v: an integer array
    @param m: An integer
    @return: an array
    """
    def back_pack_i_i_i(self, a: List[int], v: List[int], m: int) -> int:
        # write your code here
        n = len(a) 
        dp = [0 for _ in range(m+1)] # save max value
        for current_volume in range(m+1):
            for i, size in enumerate(a):
                if current_volume - size >= 0:
                    dp[current_volume] = max(dp[current_volume], dp[current_volume - size] + v[i])

        return max(dp)

算法說明

本題是背包系列問題的第 3 題，建議初學者可以從第一題開始去學：
第 1 題：最基本的背包問題，不重複 size，物品只有一個，計算組合可能性
第 2 題：最基本的背包問題，不重複 size，物品只有一個，計算最大價值
第 3 題：完全背包問題，有重複 size，物品無限數量，計算最大價值
第 4 題：有重複 size，物品無限數量，計算可能組合 ，「(1,2,3) 與 (2,3,1) 視為相同答案」
第 5 題：有重複 size，物品有限數量，計算可能組合 ，「(1,2,3) 與 (2,3,1) 視為相同答案」
第 6 題：有重複 size，物品無限數量，計算可能「排列」 ，也就是說「(1,2,3) 與 (2,3,1) 視為不同答案」
第 7 題：有重複物品，有限制物品數數量上限，問可能組合
第 8 題：有重複物品，有限制物品數數量上限，問最大價值
第 9 題：變化問題，有重複 size，計算機率
第 10 題：變化問題，只是把 size 面額提高

這題是給我們無限數量的物品可以拿，我們只提供物品的種類。

因為物品變成可以無限使用，首先我們可想像的第一個問題是，
我們的 i 比照之前方法辦理的話，會有無限個，
這時我們該怎麼辦法？

無限物品數量的思路

最簡單的方法，我們可以把 for 的內外圈對調，就可以輕鬆解決了。
我們的想法變為「背包目前最大的大小」在外圈，
「我們看到不同種類的硬幣」在內圈，因為我們可以無限取用。

拿新物品的前一個體積大小 last_volume = current_volume – size]
我們比較每次 dp[current_volume] = max(dp[current_volume], dp[last_volume] + value[此物品])，
只保留當前背包的最大價值。

input handling

一同在 dp 內處理

Boundary conditions

用兩層 for 來控制搜尋範圍，
外層 for volume (表示我們目前背包的大小，最大可能的價值)
內層 for value (表示新增價值後，保留目前容量可能的最大價值)

Reference