P1507 NASA的食物计划 (动态规划)

这篇具有很好参考价值的文章主要介绍了P1507 NASA的食物计划 (动态规划)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

#include <bits/stdc++.h>
using namespace std;
int dp[55][404][404] = {0};

int main()
{
	int v;
	int q;
	int n;
	cin >> v>> q>> n;
	int volume[55];
	int qual[55];
	int calor[55];
	for (int i = 1;i <= n;i++){
		cin>> volume[i]>> qual[i]>> calor[i];
	}
	for (int i = 1;i <= n;i++){
		for (int j = 1;j <= v;j++){
			for (int k = 1;k <= q;k++){
				if (j >= volume[i] && k >= qual[i]){
					dp[i][j][k] = max (dp[i-1][j][k] , dp[i-1][j-volume[i]][k-qual[i]] + calor[i]);               
				}
				else {
					dp[i][j][k] = dp[i-1][j][k];
				}
			}
		}
	}
	cout << dp[n][v][q];
	return 0;
}

NASA的食物计划

题目背景

NASA(美国航空航天局)因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋,因此在各方压力下终止了航天飞机的历史,但是此类事情会不会在以后发生,谁也无法保证。所以,在遇到这类航天问题时,也许只能让航天员出仓维修。但是过多的维修会消耗航天员大量的能量,因此 NASA 便想设计一种食品方案,使体积和承重有限的条件下多装载一些高卡路里的食物。

题目描述

航天飞机的体积有限,当然如果载过重的物品,燃料会浪费很多钱,每件食品都有各自的体积、质量以及所含卡路里。在告诉你体积和质量的最大值的情况下,请输出能达到的食品方案所含卡路里的最大值,当然每个食品只能使用一次。

输入格式

第一行 2 2 2 个整数,分别代表体积最大值 h h h 和质量最大值 t t t

第二行 1 1 1 个整数代表食品总数 n n n

接下来 n n n 行每行 3 3 3 个数 体积 h i h_i hi,质量 t i t_i ti,所含卡路里 k i k_i ki

输出格式

一个数,表示所能达到的最大卡路里(int 范围内)

样例 #1

样例输入 #1

320 350
4
160 40 120
80 110 240
220 70 310
40 400 220

样例输出 #1

550

提示

对于 100 % 100\% 100% 的数据, h , t , h i , t i ≤ 400 h,t,h_i,t_i \le 400 h,t,hi,ti400 n ≤ 50 n \le 50 n50 k i ≤ 500 k_i \le 500 ki500文章来源地址https://www.toymoban.com/news/detail-845749.html

到了这里,关于P1507 NASA的食物计划 (动态规划)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【洛谷 P4017】最大食物链计数 题解(深度优先搜索+动态规划+邻接表+记忆化搜索+剪枝)

    你知道食物链吗?Delia 生物考试的时候,数食物链条数的题目全都错了,因为她总是重复数了几条或漏掉了几条。于是她来就来求助你,然而你也不会啊!写一个程序来帮帮她吧。 给你一个食物网,你要求出这个食物网中最大食物链的数量。 (这里的“最大食物链”,指的

    2024年04月15日
    浏览(30)
  • 【算法思维】-- 动态规划(C++)

    OJ须知: 一般而言,OJ在1s内能接受的算法时间复杂度:10e8 ~ 10e9之间 (中值5*10e8) 。在竞赛中, 一般认为计算机1秒能执行 5*10e8 次计算 。 时间复杂度 取值范围 o(log2n) 大的离谱 O(n) 10e8 O(nlog(n)) 10e6 O(nsqrt(n))) 10e5 O(n^2) 5000 O(n^3) 300 O(2^n) 25 O(3^n) 15 O(n!) 11 时间复杂度排序: o(1

    2024年02月02日
    浏览(46)
  • C++算法 —— 动态规划(2)路径问题

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

    2024年02月06日
    浏览(49)
  • C++算法 —— 动态规划(3)多状态

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

    2024年02月09日
    浏览(38)
  • 【动态规划】C++算法312 戳气球

    视频算法专题 动态规划汇总 有 n 个气球,编号为0 到 n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果

    2024年02月03日
    浏览(41)
  • C++动态规划-线性dp算法

    莫愁千里路 自有到来风 CSDN 请求进入专栏                                    X 是否进入《 C++ 专栏》? 确定 目录  线性dp简介 斐波那契数列模型  第N个泰波那契数 思路: 代码测试:  三步问题 思路: 代码测试: 最小花费爬楼梯 思路: 代码测试:  路径问题 数字三

    2024年02月19日
    浏览(46)
  • 【动态规划】C++算法:403.青蛙过河

    视频算法专题 动态规划汇总 一只青蛙想要过河。 假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。 青蛙可以跳上石子,但是不可以跳入水中。 给你石子的位置列表 stones(用单元格序号 升序 表示), 请判定青蛙能否成功过

    2024年01月17日
    浏览(47)
  • 【动态规划】C++算法:最长有效括号

    视频算法专题 动态规划汇总 给你一个只包含 ‘(’ 和 ‘)’ 的字符串,找出最长有效(格式正确且连续)括号子串的长度。 示例 1: 输入:s = “(()” 输出:2 解释:最长有效括号子串是 “()” 示例 2: 输入:s = “)()())” 输出:4 解释:最长有效括号子串是 “()()” 示例

    2024年02月01日
    浏览(56)
  • 【动态规划】【数学】【C++算法】18赛车

    视频算法专题 动态规划汇总 数学 你的赛车可以从位置 0 开始,并且速度为 +1 ,在一条无限长的数轴上行驶。赛车也可以向负方向行驶。赛车可以按照由加速指令 ‘A’ 和倒车指令 ‘R’ 组成的指令序列自动行驶。 当收到指令 ‘A’ 时,赛车这样行驶: position += speed speed

    2024年01月19日
    浏览(45)
  • c++ 算法之动态规划—— dp 详解

    dp 是 c++ 之中一个简单而重要的算法,每一个 OIer 必备的基础算法,你知道它究竟是什么吗? 目录 一、简介         1.为什么不能贪心?         2.揭秘 dp   二、应用         1.定义         2.边界值         3.动态转移方程         4.结果         5.代码

    2024年04月09日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包