当前位置: 首页 > news >正文

Day 44 | 动态规划 完全背包、518. 零钱兑换 II 、 377. 组合总和 Ⅳ

完全背包

题目
文章讲解
视频讲解

完全背包和0-1背包的区别在于:物品是否可以重复使用

思路:对于完全背包问题,内层循环的遍历方式应该是从weight[i]开始一直遍历到V,而不是从V到weight[i]。这样可以确保每种物品可以被选择多次放入背包,从而求解完全背包问题。

对于完全背包问题,需要对内层循环进行调整,以确保每种物品可以被选择多次放入背包。

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt(); // 研究材料种类int V = sc.nextInt(); // 行李箱空间int[] values = new int[N]; // 物品价值int[] weight = new int[N]; // 物品重量// 依次输入每种物品的重量和价值for (int i = 0; i < N; i++) {weight[i] = sc.nextInt(); // 物品重量values[i] = sc.nextInt(); // 物品价值}int[] dp = new int[V + 1]; // 动态规划数组for (int i = 0; i < N; i++) {for (int j = weight[i]; j <= V; j++) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + values[i]); // 动态规划状态转移方程}}System.out.println(dp[V]); // 输出结果}
}

一维0-1背包求解法示例如下

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt(); // 研究材料种类int V = sc.nextInt(); // 行李箱空间int[] values = new int[N]; // 物品价值int[] weight = new int[N]; // 物品重量// 依次输入每种物品的重量和价值for (int i = 0; i < N; i++) {weight[i] = sc.nextInt(); // 物品重量values[i] = sc.nextInt(); // 物品价值}int[] dp = new int[V + 1]; // 动态规划数组for (int i = 0; i < N; i++) {for (int j = V; j >= weight[i]; j--) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + values[i]); // 动态规划状态转移方程}}System.out.println(dp[V]); // 输出结果}
}

对比:

  • 完全背包:
    在这里插入图片描述

  • 0-1背包:
    在这里插入图片描述

518. 零钱兑换 II

题目
文章讲解
视频讲解

思路:

  1. dp[j]:凑成总金额j的货币组合数为dp[j]
  2. 递推公式:dp[j] 就是所有的dp[j - coins[i]](考虑coins[i]的情况)相加
  3. 初始化需要注意 dp[0]=1;
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; j++) {dp[j] += dp[j - coins[i]];}}return dp[amount];}
}

377. 组合总和 Ⅳ

题目
文章讲解
视频讲解

思路:

如果求组合数就是外层for循环遍历物品,内层for遍历背包;
如果求排列数就是外层for遍历背包,内层for循环遍历物品。

class Solution {public int combinationSum4(int[] nums, int target) {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];}
}
http://www.lryc.cn/news/300984.html

相关文章:

  • 使用PaddleNLP UIE模型提取上市公司PDF公告关键信息
  • 软件工程师,OpenAI Sora驾到,快来围观
  • 【Linux 04】编辑器 vim 详细介绍
  • KMP算法详解
  • ubuntu22.04@laptop OpenCV Get Started: 013_contour_detection
  • [ai笔记5] 个人AI资讯助手实战
  • QT+OSG/osgEarth编译之八十九:osgdb_ply+Qt编译(一套代码、一套框架,跨平台编译,版本:OSG-3.6.5插件库osgdb_ply)
  • 机器人专题:我国机器人产业园区发展现状、问题、经验及建议
  • 算法沉淀——哈希算法(leetcode真题剖析)
  • 深入理解Redis哨兵原理
  • MySQL-存储过程(PROCEDURE)
  • linux系统监控工具prometheus的安装以及监控mysql
  • 初识tensorflow程序设计模式
  • 【QT+QGIS跨平台编译】之三十八:【GDAL+Qt跨平台编译】(一套代码、一套框架,跨平台编译)
  • 黑马鸿蒙教程学习1:Helloworld
  • 蓝桥杯每日一题------背包问题(四)
  • OpenAI发布Sora技术报告深度解读!真的太强了!
  • AJAX——接口文档
  • leetcode hot100不同路径
  • 【前端工程化面试题目】webpack 的热更新原理
  • 不花一分钱,在 Mac 上跑 Windows(M1/M2 版)
  • Attempt to call an undefined function glutInit
  • AB测试最小样本量
  • 在Spring中事务失效的场景
  • Rust 学习笔记 - 变量声明与使用
  • windows 下跑起大模型(llama)操作笔记
  • 人工智能专题:基础设施行业智能化的基础设施,自智网络双价值分析
  • docker 编译安装redis脚本
  • 鸿蒙开发系列教程(二十三)--List 列表操作(2)
  • C#根据权重抽取随机数