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

代码随想录二刷day46

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

文章目录

  • 前言
  • 一、力扣139. 单词拆分
  • 二、力扣动态规划:关于多重背包,你该了解这些!


前言


提示:以下是本篇文章正文内容,下面案例可供参考

一、力扣139. 单词拆分

class Solution {public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> set = new HashSet<>(wordDict);boolean[] dp = new boolean[s.length()+1];dp[0] = true;for(int i = 1; i <= s.length(); i ++){for(int j = 0; j < i && !dp[i]; j ++){if(dp[j] && set.contains(s.substring(j,i))){dp[i] = true;}}}return dp[dp.length-1];}
}

二、力扣动态规划:关于多重背包,你该了解这些!

public void testMultiPack1(){// 版本一:改变物品数量为01背包格式List<Integer> weight = new ArrayList<>(Arrays.asList(1, 3, 4));List<Integer> value = new ArrayList<>(Arrays.asList(15, 20, 30));List<Integer> nums = new ArrayList<>(Arrays.asList(2, 3, 2));int bagWeight = 10;for (int i = 0; i < nums.size(); i++) {while (nums.get(i) > 1) { // 把物品展开为iweight.add(weight.get(i));value.add(value.get(i));nums.set(i, nums.get(i) - 1);}}int[] dp = new int[bagWeight + 1];for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = bagWeight; j >= weight.get(i); j--) { // 遍历背包容量dp[j] = Math.max(dp[j], dp[j - weight.get(i)] + value.get(i));}System.out.println(Arrays.toString(dp));}
}public void testMultiPack2(){// 版本二:改变遍历个数int[] weight = new int[] {1, 3, 4};int[] value = new int[] {15, 20, 30};int[] nums = new int[] {2, 3, 2};int bagWeight = 10;int[] dp = new int[bagWeight + 1];for(int i = 0; i < weight.length; i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量// 以上为01背包,然后加一个遍历个数for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);}System.out.println(Arrays.toString(dp));}}
}
http://www.lryc.cn/news/184064.html

相关文章:

  • 计算机竞赛 行人重识别(person reid) - 机器视觉 深度学习 opencv python
  • 在线图片转BASE64、在线BASE64转图片
  • 什么是RPA?一文了解RPA发展与进程!
  • 【云备份项目】【Linux】:环境搭建(g++、json库、bundle库、httplib库)
  • 工信部教考中心:什么是《研发效能(DevOps)工程师》认证,拿到证书之后有什么作用!(下篇)丨IDCF
  • Linux进程相关管理(ps、top、kill)
  • 微服务技术栈-Ribbon负载均衡和Nacos注册中心
  • 知识图谱和大语言模型的共存之道
  • enum, sizeof, typedef
  • (二)激光线扫描-相机标定
  • pytorch 数据载入
  • angular 在vscode 下的hello world
  • Django、Nginx、uWSGI详解及配置示例
  • 王道考研计算机组成原理——计算机硬件的基础知识
  • [晕事]今天做了件晕事21;设置代理访问网站的时候需注意的问题
  • Go通过reflect.Value修改值
  • 【MySql】4- 实践篇(二)
  • 获取多个接口的数据并进行处理,使用Promise.all来等待所有接口请求完成
  • 利用C++开发一个迷你的英文单词录入和测试小程序-升级版本
  • 用c动态数组(实现权重矩阵可视化)实现手撸神经网络230902
  • Android.mk和Android.bp
  • CSS 常用样式-文本属性
  • BootstrapBlazor企业级组件库:前端开发的革新之路
  • 力扣 -- 1745. 分割回文串 IV
  • C# 给某个方法设定执行超时时间
  • 安装NodeJS并使用yarn下载前端依赖
  • (Java高级教程)第三章Java网络编程-第八节:博客系统搭建(前后端分离)
  • 901. 股票价格跨度
  • JavaScript中的模块化编程,包括CommonJS和ES6模块的区别。
  • 从零开始 Spring Cloud 13:分布式事务