Day38- 动态规划part06

news/2024/2/21 3:40:49

 一、完全背包

题目一:完全背包

52. 携带研究材料(第七期模拟笔试)

题目描述

小明是一位科学家,他需要参加一场重要的国际科学大会,以展示自己的最新研究成果。他需要带一些研究材料,但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等,它们各自占据不同的重量,并且具有不同的价值。

小明的行李箱所能承担的总重量为 N,问小明应该如何抉择,才能携带最大价值的研究材料,每种研究材料可以选择无数次,并且可以重复选择。

输入描述

第一行包含两个整数,N,V,分别表示研究材料的种类和行李空间 

接下来包含 N 行,每行两个整数 wi 和 vi,代表第 i 种研究材料的重量和价值

输出描述

输出一个整数,表示最大价值。

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int knapsack(int N, int V, vector<int>& weights, vector<int>& values) {vector<int> dp(V + 1, 0);for (int i = 0; i < N; ++i) {for (int j = weights[i]; j <= V; ++j) {dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);}}return dp[V];
}int main() {int N, V;cin >> N >> V;vector<int> weights(N);vector<int> values(N);for (int i = 0; i < N; ++i) {cin >> weights[i] >> values[i];}int result = knapsack(N, V, weights, values);cout << result << endl;return 0;
}

二、零钱兑换 II

题目一:518. 零钱兑换 II

518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

/** @lc app=leetcode.cn id=518 lang=cpp** [518] 零钱兑换 II*/// @lc code=start
class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1, 0);dp[0] = 1;for (int coin : coins) {for (int i = coin; i <= amount; ++i) {dp[i] += dp[i - coin];}}return dp[amount];}
};
// @lc code=end

三、组合总和 IV

题目一:377. 组合总和 IV

377. 组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

/** @lc app=leetcode.cn id=377 lang=cpp** [377] 组合总和 Ⅳ*/// @lc code=start
class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<unsigned int> dp(target + 1, 0);dp[0] = 1;for (int i = 1; i <= target; ++i) {for (int num : nums) {if (i >= num) {dp[i] += dp[i - num];}}}return dp[target];}
};
// @lc code=end


https://www.xjx100.cn/news/3270641.html

相关文章

Javaweb之SpringBootWeb案例之事务进阶的详细解析

1.3 事务进阶 前面我们通过spring事务管理注解Transactional已经控制了业务层方法的事务。接下来我们要来详细的介绍一下Transactional事务管理注解的使用细节。我们这里主要介绍Transactional注解当中的两个常见的属性&#xff1a; 异常回滚的属性&#xff1a;rollbackFor 事…

防火墙安全策略及nat实验

要求一&#xff1a;生产区的设备在工作时间访问dmz区,仅可访问http服务器 要求二&#xff1a;办公区可以全天访问dmz区&#xff0c;其中10.0.2.20可以访问FTP服务器和HTTP服务器&#xff0c;10.0.2.10仅可以ping通10.0.3.10 要求三&#xff1a;办公区在访问服务器区时采用匿名认…

1306. 跳跃游戏 III

经过测试&#xff0c;两种写法耗时差距10倍&#xff0c;我也不知道原因是啥 用访问次数的是更快的 class Solution { public:int n;bool dfs(vector<int>& arr, int start, vector<int>& visited){if(start<0||start>n || visited[start]1) return …

鸿蒙开发理论之页面和自定义组件生命周期

1、自定义组件和页面的关系 页面&#xff1a;即应用的UI页面。可以由一个或者多个自定义组件组成&#xff0c;Entry装饰的自定义组件为页面的入口组件&#xff0c;即页面的根节点&#xff0c;一个页面有且仅能有一个Entry。只有被Entry装饰的组件才可以调用页面的生命周期。自…

Linux(Ubuntu) 环境搭建:MySQL

注&#xff1a;服务器默认以root用户登录 服务器的终端中输入以下指令&#xff1a; # 安装 MySQL apt install mysql-server # 查看版本 mysql -V # 查看 MySQL 服务状态 systemctl status mysql # 安装完成后&#xff0c;MySQL 服务将自动启动 # MySQL 服务在系统启动时自动…

鸿蒙harmony--TypeScript类详解

今天是正月初三&#xff0c;许下三个心愿&#xff0c;一愿家人安康&#xff0c;亲人在旁&#xff0c;二愿山河无恙&#xff0c;人间皆安&#xff0c;三愿喜乐无忧&#xff0c;生活明朗&#xff0c;愿你好事接二连三&#xff0c;新年福气相伴&#xff01; 目录 一&#xff0c;类…

2024-02-08 Unity 编辑器开发之编辑器拓展1 —— 自定义菜单栏

文章目录 1 特殊文件夹 Editor2 在 Unity 菜单栏中添加自定义页签3 在 Hierarchy 窗口中添加自定义页签4 在 Project 窗口中添加自定义页签5 在菜单栏的 Component 菜单添加脚本6 在 Inspector 为脚本右键添加菜单7 加入快捷键8 小结 1 特殊文件夹 Editor ​ Editor 文件夹是 …

读千脑智能笔记10_人类智能存在的风险

1. 人类智能存在的风险 1.1. “末日时钟” 1.1.1. 核战争引发的大火列为地球毁灭的主要原因 1.1.2. 气候变化列为人类自我毁灭的第二大潜在原因 1.2. 除非我们刻意加入自私的驱动力、动机或情感&#xff0c;否则智能机器并不会威胁到人类的生存 1.2.1. 人类在不远的将来会…