算法学习笔记（8.4）-完全背包问题

目录

Question：

图例：

动态规划思路

2 代码实现：

3 空间优化：

代码实现：

下面是0-1背包和完全背包具体的例题：

代码实现：

图例：

空间优化代码示例

Question：

给定n个物品，第i个物品的重量为wgt[i-1]，价值为val[i-1],和一个容量为cap的背包。每个物品可以重复选取，问在限定背包容量的情况下能放入物品的最大价值。

图例：

1. 动态规划思路

完全背包问题和0-1背包问题非常相似，区别仅在于不限制物品的选择次数。

1. 在0-1背包问题中，每种物品只有一个，因此将物品i放入到被曝后，只能从前i-1个物品选择。
2. 在完全背包问题中，每种物品的数量都是无限的，因此将物品i放入到背包后，仍可以从前i个物品中选择。

在完全背包问题的规定下，状态[i，c]的变化分为以下两种情况。

1. 不放入物品i：与0-1背包问题相同转移至[i-1,c]。
2. 放入物品i：与0-1背包问题不同，转移至[i,c-wgt[i-1]]。

从而转移状态方程为：

dp[i，c] = max(dp[i-1,c],dp[i,c-wgt[i-1]]+val[i-1])

2 代码实现：

# python 代码示例
def unbound_knap_sack_dp(wgt, val, cap) :n = len(wgt)dp = [ [0] * (cap + 1) for _ in range(n + 1)]for i in range(1, n + 1) :for j in range(1, cap + 1) :if wgt[i - 1] > c :dp[i][c] = dp[i - 1][c]else :dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]]  + val[i - 1])return dp[n][cap]

// c++ 代码示例int unboundKnapSackDP(vector<int> &wgt, vector<int> &val, int cap)
{int n = wgt.size() ;vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0)) ;for (int i = 1 ; i <= n ; i++){for (int j = 1 ; j <= cap ; j++){if (wgt[i - 1] > c){dp[i][c] = dp[i - 1][c] ;}else{dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1) ;}}}return dp[n][cap] ;
}

3 空间优化：

由于当前状态是从左边和上边的状态转移而来，因此空间优化后应该对dp表中的每一行进行正序遍历。

图例所示：

代码实现：

# python 代码示例def unbound_knap_sack_dp_comp(wgt, val, cap) :n = len(wgt)dp = [0] * (cap + 1)for i in range(1, n + 1) :for j in range(1, cap + 1) :if wgt[i - 1] > c :dp[c] = dp[c]else :dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]) return dp[cap] ;

// c++ 代码示例int unboundKnapSackDPComp(vector<int> &wgt, vector<int> &val, int cap)
{int n = wgt.size() ;vector<int> dp(cap + 1, 0) ;for (int i = 1 ; i <= n ; i ++){for (int j = 1 ; j <= cap ; j++){if (wgt[i - 1] > c){dp[c] = dp[c] ;}else{dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]) ;}}}return dp[c] ;
}

下面是0-1背包和完全背包具体的例题：

零钱兑换问题：给定n中硬币，第i种硬币的面值为coins[i-1],目标金额为amt，每种硬币可以重复选取，问能够凑出目标金额的最少硬币数。如果无法凑出目标金额，则返回-1。

图例：

动态规划的思路：

零钱兑换可以看作是完全背包的一种特殊情况，两者具有以下联系和不同点。

1. 两道题目可以相互转化，“物品“对应”硬币“、”物品重量“对应”硬币面值“、”背包容量“对应”目标金额“。
2. 优化目标相反，完全背包问题是要最大化物品价值，零钱兑换问题是要最小化硬币数量。
3. 完全背包问题是求“不超过“背包容量下的解，零钱兑换是求”恰好“凑到目标金额的解。

第一步：思考每轮的决策，定义状态，从而得到dp表

状态[i,a]对应的子问题为：前i种硬币能够凑出金额a的最少硬币数量，记作dp[i,a]。

二维dp表的尺寸为（n+1）*（amt+1）.

第二步：找出最优子结构，进而推导出状态转移方程

本题与完全背包问题的转移状态方程存在以下两点差异。

1. 本题要求最小值，因此需将运算符max()更改为min()。
2. 优化主体是硬币数量而非商品的价值，因此在选中硬币时需执行+1即可。

dp[i,a] = min(dp[i-1,a],dp[i,a-coins[i-1]]+1)

第三步：确定边界和状态转移顺序

当目标金额为0时，凑出它的最小硬币数量为0，即首列所有dp[i，0]都等于0。

当无硬币时，无法凑出任意>0的目标金额，即使无效解。为使状态转移方程中的min()函数能够识别并过滤无效解，我们使用+∞来表示他们，即令首行所有dp[0,a]都等于+∞。

代码实现：

def coin_change_dp(coins, amt) :n = len(coins)dp = [ [0] * (amt + 1) for _ in range(n + 1)]for j in range(1, amt + 1) :dp[0][j] = inffor i in range(1, n + 1) :dp[i][0] = 0for i in range(1, n + 1) :for j in range(1, cap + 1) :if coins[i - 1] > j :dp[i][j] = dp[i - 1][j]else :dp[i][j] = max(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1)return dp[n][amt] if dp[n][amt] != inf else -1

int coinsChangeDP(vector<int> &coins, int amt)
{int n = coins.size() ;vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0)) ;for (int j = 1 ; j <= amt ; j++) {dp[0][j] = INT_MAX ;}for (int i = 1 ; i <= n ; i++){dp[i][0] = 0 ;}for (int i = 1 ; i <= n ; i++){for (int j = 1 ; j <= amt ; j++){if (coins[i - 1] > j){dp[i][j] = dp[i - 1][j] ;}else{dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1) ;}}}return dp[n][amt] != INT_MAX ? dp[n][amt] : -1 ;}

图例：

空间优化代码示例：

# python 代码示例def coins_change_dp_comp(coins, amt) :n = len(coins)dp = [inf] * (amt + 1)for i in range(1, n + 1) :for j in range(1, cap + 1) :if (coins[i - 1] > j) :dp[j] = dp[j]else :dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1)return dp[amt] if dp[amt] != inf else -1

// c++ 代码示例
int coinsChangeDPComp(vector<int> &coins, int amt)
{int n = coins.size() ;vector<int> dp(cap + 1, INT_MAX) ;for (int i = 1 ; i <= n ; i++){for (int j = 1 ; j <= amt ; j++){if (coins[i - 1] > j){dp[j] = dp[j] ;}else{dp[j] = min([j], [j - coins[i - 1]] + 1) ;}}}return dp[amt] != INT_MAX ? dp[amt] : -1 ;}