代码随想录day38：动态规划part6，完全背包

本文主要是介绍代码随想录day38：动态规划part6，完全背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- day38：动态规划part6，完全背包
- - 完全背包模板
  - 518.零钱兑换 II
  - 377.组合总和 Ⅳ

day38：动态规划part6，完全背包

完全背包模板

https://kamacoder.com/problempage.php?pid=1052

import java.util.*;class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int m = in.nextInt();int n = in.nextInt();int[] weights = new int[m];int[] values = new int[m];for (int i = 0; i < m; i++) {weights[i] = in.nextInt();values[i] = in.nextInt();}int[] dp = new int[n + 1];for (int i = 0; i < m; i++) {for (int j = weights[i]; j <= n; j++)dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);}System.out.println(dp[n]);}
}

518.零钱兑换 II

外层先遍历物品，内层再遍历背包，算组合数

class Solution {public int change(int amount, int[] coins) {// dp[j]：凑成总金额j的货币组合数int[] dp = new int[amount + 1];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];}
}

377.组合总和 Ⅳ

外层先遍历背包，内层再遍历物品，算排列数

class Solution {public int combinationSum4(int[] nums, int target) {// dp[j]：凑成目标整数j的排列个数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];}
}