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

满18点此转入2o2新乡seo公司

满18点此转入2o2,新乡seo公司,网站建设的市场,做网站测试需要学什么多1.【模板】完全背包_牛客题霸_牛客网 你有一个背包,最多能容纳的体积是V。 现在有n种物品,每种物品有任意多个,第i种物品的体积为vivi​ ,价值为wiwi​。 (1)求这个背包至多能装多大价值的物品? &#xff0…

1.【模板】完全背包_牛客题霸_牛客网

你有一个背包,最多能容纳的体积是V。

现在有n种物品,每种物品有任意多个,第i种物品的体积为vivi​ ,价值为wiwi​。

(1)求这个背包至多能装多大价值的物品?

(2)若背包恰好装满,求至多能装多大价值的物品?

输入描述:

第一行两个整数n和V,表示物品个数和背包体积。

接下来n行,每行两个数vivi​和wiwi​,表示第i种物品的体积和价值。

1≤n,V≤10001≤n,V≤1000

输出描述:

输出有两行,第一行输出第一问的答案,第二行输出第二问的答案,如果无解请输出0。

示例1

输入:

2 6
5 10
3 1
输出:
10
2

示例2

输入:

3 8
3 10
9 1
10 1
输出:
20
0

说明:

无法恰好装满背包。

示例3

输入:

6 13
13 189
17 360
19 870
14 184
6 298
16 242
输出:
596
189

说明:

可以装5号物品2个,达到最大价值298*2=596,若要求恰好装满,只能装1个1号物品,价值为189.
#include <iostream>
#include <string.h>
using namespace std;
int main()
{int n, V;cin >> n >> V;int v[n];int w[n];for (int i = 0; i < n; i++) cin >> v[i] >> w[i];int dp[n + 1][V + 1];//初始化memset(dp, 0, sizeof dp);for (int i = 1; i <= n; i++){for (int j = 0; j <= V; j++){//动态转移方程dp[i][j] = dp[i - 1][j];if (j - v[i - 1] >= 0) dp[i][j] = max(dp[i][j], dp[i][j - v[i - 1]] + w[i - 1]);}}cout << dp[n][V] << endl;memset(dp, 0, sizeof dp);for (int i = 1; i <= V; i++) dp[0][i] = -1;for (int i = 1; i <= n; i++){for (int j = 0; j <= V; j++){dp[i][j] = dp[i - 1][j];if (j - v[i - 1] >= 0 && dp[i][j - v[i - 1]] != -1) dp[i][j] = max(dp[i][j], dp[i][j - v[i - 1]] + w[i - 1]);}}cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;return 0;
}

2.零钱兑换  力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

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

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1

你可以认为每种硬币的数量是无限的。

示例 1:

输入:coins = [1, 2, 5], amount = 11
输出:3 
解释:11 = 5 + 5 + 1

示例 2:

输入:coins = [2], amount = 3
输出:-1

示例 3:

输入:coins = [1], amount = 0
输出:0
class Solution {
public:int coinChange(vector<int>& coins, int amount) {int n=coins.size();vector<int> dp(amount+1);//创建dp表for(int i=1;i<=amount;i++) dp[i]=0x3f3f3f3f;//初始化,寻找最小值for(int i=1;i<=n;i++){for(int j=coins[i-1];j<=amount;j++){if(j-coins[i-1]>=0){dp[j]=min(dp[j],dp[j-coins[i-1]]+1);//动态转移方程}}}return dp[amount]>=0x3f3f3f3f?-1:dp[amount];//返回值}
};

3.零钱兑换二  力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

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

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

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

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

示例 1:

输入:amount = 5, coins = [1, 2, 5]
输出:4
解释:有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:

输入:amount = 3, coins = [2]
输出:0
解释:只用面额 2 的硬币不能凑成总金额 3 。

示例 3:

输入:amount = 10, coins = [10] 
输出:1
class Solution {
public:int change(int amount, vector<int>& coins) {int n=coins.size();vector<int> dp(amount+1);dp[0]=1;//初始化for(int i=1;i<=n;i++){for(int j=coins[i-1];j<=amount;j++){dp[j]+=dp[j-coins[i-1]];//动态转移方程}}return dp[amount];//返回值}
};

4.完全平方数  力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,14916 都是完全平方数,而 311 不是。

示例 1:

输入:n = 12
输出:3 
解释:12 = 4 + 4 + 4

示例 2:

输入:n = 13
输出:2
解释:13 = 4 + 9
class Solution {
public:int numSquares(int n) {int m=sqrt(n);vector<int> dp(n+1,0x3f3f3f3f);//初始化dp[0]=0;for(int i=1;i<=m;i++){for(int j=i*i;j<=n;j++){dp[j]=min(dp[j],dp[j-i*i]+1);//动态转移方程}}return dp[n];       }
};

http://www.ritt.cn/news/20055.html

相关文章:

  • 政府门户网站建设问题重庆seo整站优化报价
  • 南充哪里做网站seo在线优化排名
  • 珠宝网站源码免费下载正安县网站seo优化排名
  • 想把比尔的网站封了如何做全球网站排行榜
  • 网站建站实训总结建网站找谁
  • 政府部门如何建设网站百度小说搜索热度排行榜
  • 做网站后台用什么语言网页优化公司
  • 网站建设kpi考核外贸建站服务推广公司
  • 做网站页面需要的资料搜索引擎优化网站
  • 网站瀑布流怎么做西安关键词排名首页
  • 北京短视频培训学校seo优化检测
  • 网站模板哪个网站好seo推广怎么做
  • 防爆玻璃门网站建设网址查询站长工具
  • 定制网站开发报价如何让百度快速收录网站文章
  • 网站开发的成本郑州网站技术顾问
  • 真正免费logo设计生成器seo推广方法有哪些
  • 提高网站流量软文是什么东西
  • 做视频网站要用到的服务器网络营销与策划实践报告
  • asp网站建设实录营销一体化平台
  • 用javaweb做网站seo关键词推广价格
  • bronx wordpress网站优化推广是什么
  • 无锡网站建设中国十大电商平台
  • 供热设施网站搭建教程电商运营工资一般多少钱一个月
  • 信阳做网站推广百度指数批量查询工具
  • 无锡企业网站的建设世界500强企业名单
  • 优惠券网站做淘客违规吗东莞网络营销销售
  • 做网站用什么编程语言好苏州搜索引擎排名优化商家
  • 关于网站开发的技术博客视频剪辑培训班学费一般多少
  • 织梦网站模板源码下载免费一键搭建网站
  • 网站建设服务合同模板下载网站怎么做