网站维护服务费,国内网站建设公司排名,六安建设机械网站,莱芜消息本题可以看出也是背包问题#xff0c;但区别于之前的01背包问题#xff0c;这个是完全背包问题的变形形式。
下面介绍01背包和完全背包的区别与联系#xff1a;
01背包是背包中的物品只能用一次#xff0c;不可以重复使用#xff0c;而完全背包则是可以重复使用。01/完全… 本题可以看出也是背包问题但区别于之前的01背包问题这个是完全背包问题的变形形式。
下面介绍01背包和完全背包的区别与联系
01背包是背包中的物品只能用一次不可以重复使用而完全背包则是可以重复使用。01/完全背包的递推公式这里都是以一维数组的情况举例是dp[j] Math.max(dp[j]dp[j-weight[i]]values[i])。01背包的遍历顺序是先物品再背包并且背包遍历的时候是需要倒序遍历的而完全背包则不需要直接先物品再背包背包需要正序其实先背包再物品也可以但为了方便记忆则和01保持一致。
而当在完全背包的变形形式比如本题是要求组合数组合是没有顺序的只需要找出对应的元素就可以所以递推公式是dp[j] dp[j-nums[i]]。
所以本题中我们可以想将背包中的硬币个数不限制次数的选取最后求凑成金额为amount的种类一共有多少种。
所以采用动态规划完全背包求组合情况
dp[j]表示背包容量为j的价值为dp[j]。 dp[j] dp[j-nums[i]] dp[0] 1 注意这里必须是1如果不是1的话没办法推出后面的数据后面数据就都变成0了。 遍历顺序应该先物品再背包并且背包内层循环应该由小到大遍历。 打印
class Solution {public int change(int amount, int[] coins) {//递推表达式int[] dp new int[amount 1];//初始化dp数组表示金额为0时只有一种情况也就是什么都不装dp[0] 1;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];}
}注意 如果求组合数就是外层for循环遍历物品内层for遍历背包。 如果求排列数就是外层for遍历背包内层for循环遍历物品。
