代码随想录算法训练营day44

ops/2024/9/20 15:35:54/

完全背包

完全背包和01背包的区别就是物品可以重复无限使用,因此二层循环要变为正序。

#include <iostream>
#include <vector>
using namespace std;void test_CompletePack(vector<int> weight, vector<int> value, int bagWeight) {vector<int> dp(bagWeight + 1, 0);for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量for(int i = 0; i < weight.size(); i++) { // 遍历物品if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[bagWeight] << endl;
}int main() {int N, V;cin >> N >> V;vector<int> weight;vector<int> value;for (int i = 0; i < N; i++) {int w;int v;cin >> w >> v;weight.push_back(w);value.push_back(v);}test_CompletePack(weight, value, V);return 0;
}

518. 零钱兑换 II

五部曲:

  • dp数组下标及含义:凑成总金额j的货币组合数为dp[j]
  • dp数组初始化:dp[0]=1
  • 递推公式:dp[j] += dp[j - coins[i]];
  • 遍历方向:先遍历物品在遍历背包
class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1, 0);dp[0] = 1;for (int i = 0; i < coins.size(); i++) {       for (int j = coins[i]; j <= amount; j++) { dp[j] += dp[j - coins[i]];}}return dp[amount];}
};

377. 组合总和 Ⅳ

五部曲:

  • dp数组下标及含义:凑成目标正整数j的组合数为dp[i]
  • dp数组初始化:dp[0]=1
  • 递推公式:dp[i] += dp[i - nums[j]];
  • 遍历方向:先遍历物品在遍历背包

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

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

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target + 1, 0);dp[0] = 1;for (int i = 0; i <= target; i++) {         for (int j = 0; j < nums.size(); j++) { if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {dp[i] += dp[i - nums[j]];}}}return dp[target];}
};

http://www.ppmy.cn/ops/9639.html

相关文章

笨蛋学C++【C++基础第四弹】

C基础第四弹 11.C日期&时间12.C基本的输入输出12.1I/O库头文件12.2标准输出流&#xff08;cout&#xff09;12.3标准输入流&#xff08;cin&#xff09;12.4标准错误流&#xff08;cerr&#xff09;12.5标准日志流&#xff08;clog&#xff09; 13.C结构体13.1访问结构体成…

腾讯云服务器,部署mysql数据库后无法远程访问?

一&#xff0c;首先确定自己部署的数据库&#xff0c;是否可以正常登录&#xff0c;验证部署是否是否成功 mysql -u root -p二、放开mysql远程访问权限&#xff0c;依次输入这些命令 create user root% identified with mysql_native_password by xxxxx; grant all privilege…

第07-4章 网络层详解

7.1 网络层协议 IP协议ARP&#xff08;地址解析协议&#xff09;RARP&#xff08;反向地址解析协议&#xff09;ICMP&#xff08;互联网控制消息协议&#xff09; 7.2 IP协议详解 7.2.1 IP协议功能 寻址和路由传递服务&#xff08;不可靠&#xff0c;尽最大努力&#xff0c…

呼市经开区建设服务项目水、电能耗监测 数采案例

一、项目背景及需求 项目地点位于内蒙古呼和浩特市&#xff0c;呼市数字经开区建设服务项目。属于企业用能数据采集、能耗监测板块子项目。 针对水、电能耗数据采集&#xff0c;结合现场客观因素制约&#xff0c;数据采集方面存在较大难度。大多数国网电表485接口由于封签限制…

LeetCode 2007.从双倍数组中还原原数组:哈希表——从nlogn到n

【LetMeFly】2007.从双倍数组中还原原数组&#xff1a;哈希表——从nlogn到n 力扣题目链接&#xff1a;https://leetcode.cn/problems/find-original-array-from-doubled-array/ 一个整数数组 original 可以转变成一个 双倍 数组 changed &#xff0c;转变方式为将 original …

Day16-Python基础学习之闭包和装饰器

闭包 # 闭包 def outer(logo):def inner(msg):print(f"<{logo}>{msg}<{logo}>")return inner ​ fn1 outer("Hello") # 类型是函数 注意这里传入的参数对于内部函数来说是持续存在的 fn1("world") ​ # 修改外部函数的值 def o…

BusyBox是何方神圣?

1.概念 BusyBox 是一个集成了300多个常用 Linux 命令&#xff08;例如&#xff1a;clear、mount、telnet、grep等&#xff09;和工具的单一可执行文件&#xff0c;常用于嵌入式 Linux 系统&#xff0c;如 Android。 它虽然很小&#xff0c;但提供了许多命令行的功能&#xff…

2024 应届校招经验分享(非互联网篇)

&#x1f4e2;&#x1f4e2;&#x1f4e2; 2024年应届毕业生&#xff0c;浙江大学计算机研究生。自23年秋招开始至今&#xff0c;博主先后拿到了互联网行业、机械制造行业、国企央企、高校体制等多家企业和单位的数十个Offer&#xff0c;了解多行业中的计算机求职方向&#xff…

展览展会媒体媒体邀约执行应该怎么做?

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体网胡老师。 展览展会邀请媒体跟其他活动邀请媒体流程大致相同&#xff0c;包括 制定媒体邀约计划&#xff0c;准备新闻稿&#xff0c;发送邀请函&#xff0c;确认媒体参会&#xff0c;现场媒体接待及…

《大话西游2》本人收集的十二个单机版游戏,有详细的视频架设教程,云盘下载

《大话西游2》是一款经典的大型多人在线角色扮演游戏&#xff0c;也是一款国风经典的游戏。 有能力的可以架设个外网&#xff0c;让大家一起玩。 《大话西游2》本人收集的十二个单机版游戏&#xff0c;有详细的视频架设教程&#xff0c;值得收藏 下载地址&#xff1a; 链接&…

数据分析_数据分析思维(1)

数据分析_数据分析思维(1) 这篇文章具体的给大家介绍数据分析中最为核心的技术之一: 数据分析思维的相关内容。 一、数据分析的三种核心思维 作为新手数据分析师或数据运营, 在面对数据异常的时候, 好多小伙伴都会出现: “好像是A引起的”, “好像也和B渠道有关”, “也可能…

LocalAi,Ollama+AnythingLLM搭建部署本地大模型AI知识库,汉化版本

AnythingLLM 是一个全栈应用程序&#xff0c;您可以使用商业现成的 LLM 或流行的开源 LLM 和 vectorDB 解决方案来构建私有 ChatGPT&#xff0c;无需任何妥协&#xff0c;您可以在本地运行&#xff0c;也可以远程托管并能够智能聊天以及您提供的任何文件。 AnythingLLM 将您的文…

物理机中没有VMNet1和VMNet8虚拟网卡

控制面板——网络连接——网络适配器 VMware Network Adapter VMnet1 VMware Network Adapter VMnet8 如果没有这两个虚拟网卡&#xff0c;虚拟机的网络会出现问题 # 解决办法-恢复虚拟网卡默认设置 1、下载并打开ccleaner&#xff0c;ccleaner官网&#xff1a;CCleaner M…

【InternLM 实战营第二期笔记04】XTuner微调LLM:1.8B、多模态、Agent

一、微调的原因 大模型微调&#xff08;Fine-tuning&#xff09;的原因主要有以下几点&#xff1a; 适应特定任务&#xff1a;预训练的大模型往往是在大量通用数据上训练的&#xff0c;虽然具有强大的表示学习能力&#xff0c;但可能并不直接适用于特定的下游任务。通过微调&…

【学习笔记】Vue3源码解析:第四部分- runtime-dom(2)

课程地址&#xff1a;【已完结】全网最详细Vue3源码解析&#xff01;&#xff08;一行行带你手写Vue3源码&#xff09; 第四部分-&#xff1a;&#xff08;对应课程的第27-28节&#xff09; 第27节&#xff1a;《事件的处理》 1、在 event.ts 中编写如下代码&#xff1a;由于…

SEW减速机参数查询 2-2 实践

首先说说结论&#xff1a;在不和SEW官方取得沟通之前&#xff0c;你几乎无法直接通过查阅SEW官方文档得到相关减速机的所有技术参数&#xff1a;比如轴的模数和齿数&#xff0c;轴承的参数。我在周一耗费了一个上午&#xff0c;最终和SEW方面确认后才知晓相关技术参数需要凭借销…

针对窗口数量多导致窗口大小显示受限制的问题,使用滚动条控制窗口

建议&#xff1a;首先观察结果展示&#xff0c;判断是否可以满足你的需求。 目录 1. 问题分析 2. 解决方案 2.1 界面设计 2.2 生成代码 2.3 源码实现 3. 结果展示 1. 问题分析 项目需要显示的窗口数量颇多&#xff0c;主界面中&#xff0c;如果一次性显示全部窗口&#x…

rst文件是什么?如何阅读rst文件

左手编程&#xff0c;右手年华。大家好&#xff0c;我是一点&#xff0c;关注我&#xff0c;带你走入编程的世界。 公众号&#xff1a;一点sir&#xff0c;关注领取编程资料 如果有阅读过Python源码的同学一定知道&#xff0c;Python社区的相关的帮助文件是用rst结尾的文档格式…

kafka 的零拷贝原理

在实际应用中&#xff0c;如果我们需要把磁盘中的某个文件内容发送到远程服务器上&#xff0c;那么它必须经过几个拷贝的过程。 从磁盘中读取目标文件内容拷贝到内核缓冲区CPU 控制器再把内核缓冲区的数据赋值到用户空间的缓冲区中接着在应用程序中&#xff0c;调用 write(&am…

文心一言与GPT-4全面对比——人工智能语言模型的新纪元

随着人工智能领域的快速发展&#xff0c;各种高级语言模型相继问世&#xff0c;它们在文本生成、自然语言理解、对话系统等多个方面展示了惊人的能力。其中&#xff0c;最为瞩目的便是OpenAI发布的GPT-4和国内百度的文心一言。这两个模型都被设计用来处理复杂的语言理解和生成任…