转载

完全背包

完全背包

题意

有 N 种物品和一个容量为 V 的背包,每种物品都有无限件可用。放入第 i 种物品
的费用是 Ci,价值是 Wi。求解:将哪些物品装入背包,可使这些物品的耗费的费用总
和不超过背包容量,且价值总和最大。

分析

完全背包和0/1背包的不同之处在于每件物品有无限件可用,而不是一件。

状态转移方程为
f ( n , m )   =   m a x { f ( n + 1 , m ) , f ( n , m ? w n ) + v n }          m > = w n          f ( n , m ) =    f ( n + 1 , m )      m < w n f(n,m)\ = \ max\{f(n+1,m), f(n,m-w_n)+v_n\} \ \ \ \ \ \ \ \ m>=w_n \\ \ \ \ \ \ \ \ \ f(n,m)=\ \ f(n+1,m) \ \ \ \ m < w_n
f ( n , m ) f(n,m) 代表对于后a_n, a_n+1, …个物品的最优值 v n , w n v_n, w_n 分别是第n个物品的价值和重量

注意到状态转移方程是 f ( n , m ? w n ) + v n f(n,m-w_n)+v_n 不是 f ( n + 1 , m ? w n ) + v n f(n+1, m-w_n)+v_n

这代表着在针对第 n n 个物品,可以加无限件 n n 物品

同时代码实现的时候是顺序区别于0/1背包的顺序(滚动数组的方式)

leetcode 322就是一个完全背包的题目

python代码如下

class Solution:
    def coinChange(self, coins, amount):
        """ :type coins: List[int] :type amount: int :rtype: int """
        arr = [-1 for i in range(0, amount+1)]
        
        arr[0] = 0
        
        for i in range(0,len(coins))[::-1]:
            #一定是顺序不是逆序
            for j in range(1, amount+1):
                
                if j >= coins[i] and arr[j-coins[i]] != -1:
                    if arr[j] != -1:
                        arr[j] = min(arr[j], arr[j-coins[i]] + 1)
                    else:
                        arr[j] = arr[j-coins[i]] + 1
        
        return arr[amount]
正文到此结束
本文目录