1. 完全背包問題概念
-
問題描述：
1）有N件物品和一個(gè)最多能背重量為W的背包。第i件物品的重量是weight[i]，得到的價(jià)值是value[i] 。
2）每件物品都有無限個(gè)（也就是可以放入背包多次）（比0-1背包多出的條件）
3） 求解將哪些物品裝入背包里物品價(jià)值總和最大。 -
求解步驟：
1）首先遍歷物品，然后遍歷重量，都是從小到大遍歷，順序沒有關(guān)系（因?yàn)樾詢r(jià)比最高的只有一個(gè)）
2. 完全背包問題第一種：求最大價(jià)值（和題目描述一致）
- 代碼
//1. 先遍歷物品，再遍歷重量最常見，也更好理解一點(diǎn)
public class demo2 {
public static void main(String[] args) {
int[] weight = new int[]{1, 3, 4};
int[] value = new int[]{15, 20, 30};
int maxweight = 4;
//1）dp數(shù)組的定義，默認(rèn)初始化零
int[] dp = new int[maxweight + 1];
//2)遍歷和迭代：先物品再重量，是正序
for (int i = 0; i < weight.length; i++) {
for (int j = weight[i]; j <= maxweight ; j++) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
System.out.println("dp=" + Arrays.toString(dp));
}
}
//2. 先遍歷重量，再遍歷物品
public class demo2 {
public static void main(String[] args) {
int[] weight = new int[]{1, 3, 4};
int[] value = new int[]{15, 20, 30};
int maxweight = 4;
//1）dp數(shù)組的定義，默認(rèn)初始化零
int[] dp = new int[maxweight + 1];
//2)遍歷和迭代：先重量再物品，是正序
for (int j = 0; j <= maxweight ; j++) {
for (int i = 0; i < weight.length; i++) {
if(j>=weight[i]) dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
System.out.println("dp=" + Arrays.toString(dp));
}
}
3. 完全背包問題第二種：求最多的組合（類似0-1第二種）
題目描述：容量為k背包，存放物品int[] coins，裝滿有多少種可能性(每種物品有無限個(gè)）
注意：遍歷先物品還是先重量是有區(qū)別的：
1）先物品再重量，那么就是組合數(shù)
//1. 求組成的種類，因?yàn)槭峭耆嘲手亓恳彩菑男〉酱?/span>
public int change(int amount, int[] coins) {
//1)dp數(shù)組的定義和初始化
int[] dp =new int[amount+1];
dp[0]=1;
//2)dp數(shù)組遍歷和迭代 //迭代公式一定要記住，是一個(gè)累加的過程。
for(int i=0;i<coins.length;i++){
for(int j=coins[i];j<=amount;j++){
dp[j]+=dp[j-coins[i]];
}
}
return dp[amount];
}
1）先重量再物品，那么就是排列數(shù)
//1. 求組成的種類，因?yàn)槭峭耆嘲?，故重量也是從小到?/span>
public int change(int amount, int[] coins) {
//1)dp數(shù)組的定義和初始化
int[] dp =new int[amount+1];
dp[0]=1;
//2)dp數(shù)組遍歷和迭代 //迭代公式一定要記住，是一個(gè)累加的過程。
for(int j=0;j<=amount;j++){
for(int i=0;i<coins.length;i++){
if(j>=coins[i]) dp[j]+=dp[j-coins[i]];
}
}
return dp[amount];
}
4. 完全背包的總結(jié)
4.1 第一類完全背包問題：：求最大價(jià)值
1）問題描述：若干個(gè)物品，每個(gè)物品有對應(yīng)的重量和價(jià)值，當(dāng)背包大小固定為K時(shí)，如何裝存物品，使得背包中物品的價(jià)值最大？其中同一種物品的個(gè)數(shù)不限制。
2）求解方法：
（1）：用一維dp數(shù)組：使用默認(rèn)初值0；雙層遍歷，先正序遍歷物品，再正序遍歷重量或者先正序遍歷重量，再逆序遍歷物品，兩種遍歷方向都可以，但是必須都為正序遍歷。
4.2 第二類完全背包問題：裝滿可能性
1）問題描述：容量為k背包，存放物品，裝滿有多少種可能性？其中同一種物品的個(gè)數(shù)不限制。
2）求解方法：
（1）：用一維dp數(shù)組：dp[0]=1；雙層遍歷
先正序遍歷物品，再正序遍歷重量,迭代方法為累加,求的是組合數(shù)；
先正序遍歷重量，再正序遍歷物品,迭代方法為累加,求的是排列數(shù)。
4.3 0-1背包和完全背包的區(qū)別：就在重量是否是正逆序上面。
第一題：518.零錢兌換II（完全背包第二類問題：組合數(shù)）
- 題目描述
```
2. 步驟
1）就是第二類完全背包問題，求背包滿的種類數(shù)，只是這里用了組合數(shù)，所以需要先遍歷物品，再遍歷重量。
4. 代碼
```java
//1. 求組成的種類，因?yàn)槭峭耆嘲?，故重量也是從小到? public int change(int amount, int[] coins) {
//1)dp數(shù)組的定義和初始化
int[] dp =new int[amount+1];
dp[0]=1;
//2)dp數(shù)組遍歷和迭代 //迭代公式一定要記住，是一個(gè)累加的過程。//先物品再重量
for(int i=0;i<coins.length;i++){
for(int j=coins[i];j<=amount;j++){
dp[j]= dp[j-coins[i]] + dp[j];
}
}
return dp[amount];
}
第二題：377.組合總和IV（完全背包第二類問題，考慮排列數(shù)）
-
題目描述
-
解題步驟
1）就是第二類完全背包問題，求背包滿的種類數(shù)，只是這里用了排列數(shù)，所以需要先遍歷重量，再遍歷物品。文章來源：http://www.zghlxwxcb.cn/news/detail-412139.html -
代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-412139.html
public int combinationSum4(int[] nums, int target) {
//定義dp數(shù)組，并初始化
int[] dp=new int[target+1];
dp[0]=1;
//迭代遍歷：先金額，再硬幣種類
for(int i=0;i<=target;i++){
for(int j=0;j<nums.length;j++){
if(i>=nums[j]) dp[i]+=dp[i-nums[j]];
}
}
return dp[target];
}
第三題：70.爬樓梯（完全背包第二類問題，考慮排列數(shù)）
- 題目描述
- 解題思路
1）這是之前出現(xiàn)的一道題目，用斐波那契算法類似的。
2）也可以從完全背包方面進(jìn)行解析。 - 代碼
//以前的思路
public int climbStairs(int n) {
//1）斐波那契算法
int[] dp=new int[n+1];
if(n<=2) return n;
dp[0]=0;
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
//完全背包的思路
public int climbStairs(int n) {
//完全背包問題:兩個(gè)物體【1和2】，背包的大小為n,物品的個(gè)數(shù)為無限
//求解符合要求的情況有多少種，求排列數(shù)
//1)dp數(shù)組的定義和初始化
int[] dp=new int[n+1];
dp[0]=1;
//2）遍歷和迭代:先背包，后物品，正序
for(int i=0;i<=n;i++ ){
for(int j=1;j<=2;j++){
if(i>=j) dp[i]+=dp[i-j];
}
}
return dp[n];
}
第四題：322.零錢兌換（完全背包第一類問題，求最小值）
- 題目描述
- 解題步驟
1）先遍歷物品，再遍歷錢；
2）dp[ i] 數(shù)組的含義為：為了湊成總金額所需的最少硬幣個(gè)數(shù)
3）迭代公式：
（1）：加入硬幣i,故其硬幣總數(shù)為：dp[ j-weight[ i ] ]+1
（2）：不加入硬幣i,故其硬幣維持之前的為：dp[ j ] - 代碼
class Solution {
public int coinChange(int[] coins, int amount) {
//核心思路：這是一個(gè)典型的完全背包問題，兩層遍歷，從前向后，只是迭代公式不一樣
//迭代公式：dp[j]=Math.min(dp[j],dp[j-coins[i]]+1)
//dp數(shù)組的新建和初始化(第一個(gè)為0，剩下的初始為最大值max)
int max=Integer.MAX_VALUE;
int[] dp=new int[amount+1];
for(int i=1;i<amount+1;i++){
dp[i]=max;
}
//System.out.println("dp1="+ Arrays.toString(dp));
//遍歷（沒有順序）
for(int i=0;i<coins.length;i++){
for(int j=coins[i];j<=amount;j++){
//易錯(cuò)點(diǎn)：如果退回去的值dp[j-coins[i]]=max,那么這一步就不算數(shù)
if(dp[j-coins[i]]!=max) dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
}
//System.out.println("dp="+ Arrays.toString(dp));
}
//返回判斷：如果最后時(shí)max,則不能夠組成
return dp[amount]==max?-1 : dp[amount] ;
}
}
- 注意點(diǎn)：
1）初始化數(shù)組的時(shí)候，因?yàn)橐容^的是最小值，所以第一個(gè)值初始化為0，后面的初始化應(yīng)該為比較大的值（相對于于比較最大值的區(qū)別）
2）在中間比較的時(shí)候，當(dāng)之前的硬幣數(shù)數(shù)有效時(shí)，即不是初始值的時(shí)候，才是有效的，進(jìn)行判斷才有價(jià)值。
第五題：279.完全平方數(shù)（完全背包第一類問題，求最小值）
- 題目描述
- 解題步驟
1）此題和上一題一模一樣，只是需要通過給定的n，然后自己給出物品數(shù)組 - 代碼
class Solution {
public int numSquares(int n) {
//1）根據(jù)給定的值，得出物品的集合
int[] things=new int[n+1];
for(int i=1;i<=n;i++) things[i]=i*i;
//System.out.println(Arrays.toString(things));
//2)初始化dp數(shù)組
int max=Integer.MAX_VALUE;
int[] dp=new int[n+1];
for(int i=1;i<=n;i++) dp[i]=max;
//System.out.println(Arrays.toString(dp));
//3)遍歷和迭代
for(int i=1;i<=n;i++){
for(int j=things[i];j<=n;j++){
if(dp[j-things[i]]!=max) dp[ j ]=Math.min(dp[j-things[i]]+1, dp[j]);
}
}
//4）輸出
return dp[n];
}
}
第六題：139.單詞拆分？（完全背包第一類問題，求可能不可能）
- 題目描述
- 解題步驟
1）dp[i] :即從0-i個(gè)字符，是否都在wordDict里面能夠找到對應(yīng)的值；可能是全部，可能是一部分。
2）迭代公式：
（1）：把s的前i個(gè)字符分為兩部分：如果前面一部分已經(jīng)判斷能夠找到，剩下的一部分能夠湊成一個(gè)單詞，那么就可以判定為true了。
3）遍歷順序：遍歷背包放在外循環(huán)，將遍歷物品放在內(nèi)循環(huán)。內(nèi)循環(huán)從前到后。 - 代碼
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
//完全背包問題:數(shù)組就是硬幣,字符串就是金錢
//1)數(shù)組的定義和初始化:boolean[] 默認(rèn)值為false;
boolean[] dp=new boolean[s.length()+1];
dp[0]=true; //dp[0]=true;
//2)遍歷迭代：先重量，后物品
for(int i=1;i<=s.length();i++){ //**遍歷背包**
for(int j=0;j<i;j++) //**遍歷物品**
//前一部分 dp[j]=s.substring(0,j+1)在字典中能夠找到
//后一部分：wordDoct.contains(s.substring(j,i) 能夠找到對應(yīng)的單詞
if( dp[j] && wordDict.contains(s.substring(j,i)) ) dp[i]=true;
}
//3)輸出：
return dp[s.length()];
}
}
7. 多重背包問題
- 有N種物品和一個(gè)容量為V 的背包。第i種物品最多有Mi件可用，每件耗費(fèi)的空間是Ci ，價(jià)值是Wi 。求解將哪些物品裝入背包可使這些物品的耗費(fèi)的空間 總和不超過背包容量，且價(jià)值總和最大。
- 與0-1背包問題區(qū)別：0-1背包問題每件物品個(gè)數(shù)為1，而多重背包為設(shè)定的值x
- 求解思路：直接在0-1背包問題上面進(jìn)行改寫：先遍歷物品，再遍歷重量，然后再加一層循環(huán)，即遍歷物品的個(gè)數(shù)，就可以解出來了。
8. 總結(jié)：
- 完全背包第二類問題：求解裝滿背包的種類：
（0）：迭代公式：dp[j] += dp[j - nums[i]]
（1）：組合數(shù)：518.零錢兌換II
（2）：排列數(shù)：377.組合總和IV，70.爬樓梯 - 完全背包第一類問題：問裝滿背包所有物品的最小個(gè)數(shù)：
（0）：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
（1）：322.零錢兌換
（2）：279. 完全平方數(shù)
到了這里，關(guān)于力扣刷題-動(dòng)態(tài)規(guī)劃算法3：完全背包問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
