代码随想录第三十七天（完全背包问题）|完全背包|零钱兑换 II|组合总和 Ⅳ

本文主要是介绍代码随想录第三十七天（完全背包问题）|完全背包|零钱兑换 II|组合总和 Ⅳ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

完全背包问题

完全背包问题和01背包的区别就在于每一个物品可取的次数，01背包每个物品只能取一次，完全背包每个物品能取无数次。

而01背包为了保证每个物品只取一次，在遍历背包的时候需要倒序遍历，这样才能保证之前的状态都是初始状态，没有添加过物品，利用之前的状态时就不会将同一个物品进行重复添加。

在完全背包中，就需要每个物品能取多次，于是解除遍历背包时的倒序限制就行。

import java.util.*;
public class Main{public static void main (String[] args) {Scanner sc=new Scanner(System.in);int M=sc.nextInt();int N=sc.nextInt();int[] weight=new int[M];int[] value=new int[M];int bagsize=N;for(int i=0;i<M;i++){weight[i]=sc.nextInt();value[i]=sc.nextInt();}maxValue(weight,value,bagsize);}public static void maxValue(int[] weight,int[] value,int bagsize){int[] dp=new int[bagsize+1];for(int i=0;i<weight.length;i++){for(int j=weight[i];j<bagsize+1;j++){dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]);}}System.out.println(dp[bagsize]);}
}

在完全背包中，在求装满指定容量背包的组合总数的时候，遍历顺序非常重要，只求组合总数的话，先遍历物品，后遍历背包，因为先遍历物品的话，每次都会将前一个物品先添加进去，只会出现{1,2}这样的组合，不会出现{2,1}的组合。因为当前物品层依赖上一个物品层传递下来的状态，上一个物品层，就只会又上一个物品层和其之前的物品层的组合。不会有之后物品层的值放入组合中。

而将遍历顺序颠倒，先遍历背包，后遍历物品，以物品{1,2,3}为例，装满容量为4的背包，y轴为物品，x轴为背包。

	0	1	2	3	4
0	1	1	1	2	4
1	1	1	2	3	6
2	1	1	2	4	7

当背包容量为3，假如已取物品1，也就是先放入重量为2的物品，剩余只能取重量为1的组合了，就出现了{2,1}，而假如已取的是物品0，也就是先放入重量为1的物品，剩余只能取重量为2的组合，因为在上一个状态遍历了物品1，已经有了重量2的组合，就出现了{1,2}和{1,1,1}的组合了。

零钱兑换 II

题中只要求求组合总数，不讲究顺序。

动规五部曲，改变下遍历顺序

class Solution {public int change(int amount, int[] coins) {int[] dp=new int[amount+1];dp[0]=1;for(int i=0;i<coins.length;i++){for(int j=coins[i];j<amount+1;j++){dp[j]+=dp[j-coins[i]];}}return dp[amount];}
}

组合总和 Ⅳ

讲究顺序

class Solution {public int combinationSum4(int[] nums, int target) {int[] dp=new int[target+1];dp[0]=1;for(int j=1;j<target+1;j++){for(int i=0;i<nums.length;i++){if(j>=nums[i]){dp[j]+=dp[j-nums[i]];}}}return dp[target];}
}

这篇关于代码随想录第三十七天（完全背包问题）|完全背包|零钱兑换 II|组合总和 Ⅳ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---