首页 > 试题广场 >

牛妹的春游

[编程题]牛妹的春游
  • 热度指数：606 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出两个正整数x，y，另给出若干个数对[ai,bi,ci]，请挑选若干数对使得挑出的数对ai的和不小于x，bi的和不小于y，计算挑出数对的ci的和的最小值

注：
每个数对只能挑选一次，x和y均小于2000
示例1

输入

5,60,[[3,36,120],[10,25,129],[5,50,250],[1,45,130],[4,20,119]]

输出

249

说明

挑选第一和第二个数对

备注:
每种大包装只能最多买一个，所需面包breadNum、饮料的总量beverageNum均不超过2000
牛妹一定能找到满足要求的方案让大家能够出游。
算法知识视频讲解
开通博客
头像 冲刺冲
发表于 2020-07-09 23:07:37
这是道二维费用的背包问题，可以像01背包一样优化掉第一维的决策，选或不选这个袋子，然后需要像01背包一样倒序循环体积，和01背包的优化一样。其次，这道题的难点是可以买多，只要买够就行，我们只需要对负数的体积取0就行，表示我们即使当前需要的饮料小于袋子中的饮料数量，我们依然可以购买，只要从0决策转移过 展开全文
去ta的博客 赞 (6) 回复(3) 收起
头像 简单666
发表于 2021-08-28 16:21:03
题意： 有若干个物品，每个物品有两种费用 和一个价值 , 现在给你两个数字 和 ，每种物品可以选也可以不选，让你找到一种组合物品的方案，使得 并且 且 最小。 方法一（暴力DFS，不可AC） 依次递归地考虑每个物品 选/不选，最后统计符合要求的答案求最小值即可。 具体 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 泪无声呢
发表于 2021-08-26 10:01:47
牛妹的春游 描述 给出两个正整数x，y，另给出若干个数对，请挑选若干数对使得挑出的数对的和不小于x，的和不小于y，计算挑出数对的的和的最小值 注： 每个数对只能挑选一次，x和y均小于2000 方法一 思路分析 本题可以抽象为动态规划中的经典问题--背包问题 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 xqxls
发表于 2021-08-28 22:07:05
题意整理 给定x，y，以及若干数对[ai,bi,ci]。 从中选出部分数对，使得ai数对的和不小于x，bi数对的和不小于y，求最小的ci数对的和。 方法一（动态规划） 1.解题思路 状态定义：dp[i][j][k]表示选择包装数为i，面包数为j，饮料数为k的情况下，最小的花费。 状态初始化：不 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
难度：
2条回答 2289浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号