代码随想录 Day44 - 动态规划（六）

2023-08-20
江苏
本文字数：1029 字
阅读完需：约 3 分钟

相关理论

完全背包概念

有 N 件物品和一个容量为 W 的背包，第 i 件物品的重量是 weight[i]，得到的价值是 value[i]，每一件物品都有无限多个，求解怎么放置物品，可以获得的物品价值最大？

与 0-1 背包区别

0-1 背包核心代码，二维数组，物品和背包重量的遍历可以颠倒，一维数组，必须是先遍历物品，后遍历背包容量。

for(int i = 0; i < weight.size(); i++) { 	 // 遍历物品	for(int j = bagWeight; j >= weight[i]; j--) {  // 遍历背包重量    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);  }}

复制代码

完全背包核心代码，一维数组遍历顺序也可以颠倒。

for(int i = 0; i < weight.size(); i++) { // 遍历物品  for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);  }}

复制代码

作业题

322. 零钱兑换

class Solution {    public int coinChange(int[] coins, int amount) {        int[] dp = new int[amount + 1];        Arrays.fill(dp, Integer.MAX_VALUE);        dp[0] = 0;        for(int i = 0; i < coins.length; i++) {            for(int j = coins[i]; j <= amount; j++) {                if (dp[j - coins[i]] != Integer.MAX_VALUE) {                    //选择硬币数目最小的情况                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);                }            }        }        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];    }}

复制代码

279. 完全平方数

package jjn.carl.dp;
import java.util.Arrays;import java.util.Scanner;
/** * @author Jiang Jining * @since 2023-08-20 22:59 */public class LeetCode279 {        public int numSquares(int n) {        int[] dp = new int[n + 1];        Arrays.fill(dp, Integer.MAX_VALUE);        dp[0] = 0;        int max = (int) Math.sqrt(n);        for (int i = 1; i <= max; i++) {            for (int j = i * i; j <= n; j++) {                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);            }        }        return dp[n];    }        public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();        int numSquares = new LeetCode279().numSquares(n);        System.out.println(numSquares);    }}

复制代码

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/e06e82331acf188a39c5efe94】。

jjn0703

关注

Java工程师/终身学习者 2018-03-26 加入

USTC硕士/健身健美爱好者/Java工程师.

发布

暂无评论

创作场景

代码随想录 Day44 - 动态规划（六）

相关理论

完全背包概念

与 0-1 背包区别

作业题

322. 零钱兑换

279. 完全平方数

jjn0703

评论