首页 > 牛妹的春游
开通博客写题解
头像 冲刺冲
发表于 2020-07-09 23:07:37
这是道二维费用的背包问题，可以像01背包一样优化掉第一维的决策，选或不选这个袋子，然后需要像01背包一样倒序循环体积，和01背包的优化一样。其次，这道题的难点是可以买多，只要买够就行，我们只需要对负数的体积取0就行，表示我们即使当前需要的饮料小于袋子中的饮料数量，我们依然可以购买，只要从0决策转移过 展开全文
去ta的博客 赞 (6) 回复(3) 收起
头像 elkkkk
发表于 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) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”