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

代码随想录算法训练营第51天 | 139.单词拆分 多重背包理论基础

单词拆分

Alt
这道题最后是判断能否组成,很像回溯法的问题形式,和分割回文串那道题比较类似,所以是可以用回溯法解决的,但是回溯法需要使用记忆化递归来避免超时。

class Solution{
public:bool backtracking(const string s, const unordered_set<string>& wordSet, vector<bool>& memory, int startIndex){if(startIndex == s.size()){return true;}// 如果当前位置的memory数组已经更新,直接用memory的结果,不必再一次计算if(!memory[startIndex])  return memory[startIndex];for(int i = startIndex; i < s.size(); i++) {string word = s.substr(startIndex, i - startIndex + 1);if(wordSet.find(word) != wordSet.end() && backtracking(s, wordSet, memory, i + 1)){return true;}}// startIndex位置开始的字符串无法由给定的字符串组成,记录下来memory[startIndex] = false;  return false;}bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> memory(s.size(), 1);return backtracking(s, wordSet, memory, 0);}
};

动态规划方法

因为给定的字符串可以重复使用,所以是完全背包。
dp[i]:长度为 i 的字符串,如果可以被拆分成给定的那些字符串,那么dp[i] = true
递推公式:遍历小于 i 的整数 j,如果dp[j] = true,说明在下标j - 1之前的字符串已经符合要求,同时再满足 [j, i) 的字符串可以在给定数组中找到,那么就可以给 dp[i] 赋值 true。
遍历顺序:匹配字符串是要限制顺序的,所以应该先背包后物品。

class Solution{
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, false);dp[0] = true;  // 为了递推能够有效地进行for(int i = 1; i <= s.size(); i++) {for(int j = 0; j < i; j++) {  // 由于涉及到字符串的索引,同时这里i是长度j是下标,循环结束的判断条件应该自己模拟一下再决定string word = s.substr(j, i - j);if(dp[j] && wordSet.find(word) != wordSet.end()){  // 两项都满足dp[i] = true;}}}return dp[s.size()];}
};

多重背包理论基础

Alt
多重背包物品的数目是有限个,我们在遍历的过程中就需要针对某物品考虑到底选几个的问题。方法就是将有多个的物品拆开,这样每一个物品又仅有一个了,多重背包就转化为了01背包。但是这样操作容易超时,可以将遍历物品数目的循环加入到dp数组递推中。

#include <bits/stdc++.h>
using namespace std;
int main() {int bagSize, n;while(cin >> bagSize >> n) {vector<int> weight(n, 0);vector<int> value(n, 0);vector<int> nums(n, 0);for(int i = 0; i < n; i++)  cin >> weight[i];for(int i = 0; i < n; i++)  cin >> value[i];for(int i = 0; i < n; i++)  cin >> nums[i];vector<int> dp(bagSize + 1, 0);for(int i = 0; i < n; i++) {for(int j = bagSize; j >= weight[i]; j--) {for(int k = 1; k <= nums[i] && k * weight[i] <= j; k++) {dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);}}}cout << dp[bagSize] << endl;}
}
http://www.lryc.cn/news/300211.html

相关文章:

  • weilai8游戏爬虫
  • 【Java程序设计】【C00261】基于Springboot的休闲娱乐代理售票系统(有论文)
  • 【Linux】学习-基础IO拓展篇
  • 算法详解(力扣141——环形链表系列)
  • 浅谈路由器交换结构
  • Linux第51步_移植ST公司的linux内核第3步_添加修改设备树
  • 【PyTorch】PyTorch中张量(Tensor)统计操作
  • 安卓游戏开发框架应用场景以及优劣分析
  • 单片机学习笔记---LCD1602
  • django中实现适配器模式
  • 题记(42)--EXCEL排序
  • 【学网攻】 第(28)节 -- OSPF虚链路
  • 百面嵌入式专栏(面试题)驱动开发面试题汇总1.0
  • Starknet 的 JavaScript 库:Starknet.js、get-starknet和starknet-react
  • debian11 安装 k8s,containerd ,阿里云镜像(已成功)
  • Spring Task定时任务
  • 【设计模式】23中设计模式笔记
  • 类加载过程介绍
  • pytorch创建模型方式
  • MySQL 基础知识(五)之数据增删改
  • 紫微斗数双星组合:廉贞天府在辰戌
  • 人工智能|深度学习——基于全局注意力的改进YOLOv7-AC的水下场景目标检测系统
  • 使用 C++23 从零实现 RISC-V 模拟器(1):最简CPU
  • 顺序表、链表(ArrayList、LinkedList)
  • 第11讲投票创建后端实现
  • SNMP 简单网络管理协议、网络管理
  • 计算机设计大赛 深度学习YOLOv5车辆颜色识别检测 - python opencv
  • OpenCV-36 多边形逼近与凸包
  • transformer中的QKV是如何得到的?
  • console.log导致内存泄露 打包时自动去掉console.log方法