POJ2976 Dropping tests——P4377 [USACO18OPEN] Talent Show G 【分数规划二分法+贪心/背包】

2024-04-12 13:52

文章标签 规划贪心背包 tests 二分法分数 show talent dropping poj2976 p4377 usaco18open

本文主要是介绍POJ2976 Dropping tests——P4377 [USACO18OPEN] Talent Show G 【分数规划二分法+贪心/背包】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

POJ2976 Dropping tests 【分数规划二分法+贪心】
有 n 个物品，每个物品有两个权值 a 和b。你可以放弃 k 个物品，选 n-k 个物品，使得 $\frac{\sum a}{\sum b}$ 最大。
输入多个样例，第一行输入n 和 k，第二行输入n 个 ai ,第三行输入 n 个 bi，输入 0 0 结束。
输出答案乘100 后四舍五入到整数的值。
数据范围：1<=n<=1000，0<=k<n，0<=ai<=bi<=10^9。
样例输入
3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0
样例输出
83
100

题解思路：
二分一个答案 x，

$\frac{\sum w_{i}\cdot a_{i}}{\sum w_{i}\cdot (a_{i}\cdot xb_{i})}\geq x$

这篇关于POJ2976 Dropping tests——P4377 [USACO18OPEN] Talent Show G 【分数规划二分法+贪心/背包】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

http://www.chinasem.cn/article/897313。 23002807@qq.com

相关文章

poj2576(二维背包)

poj2576(二维背包)

题意：n个人分成两组，两组人数只差小于1 ，并且体重只差最小对于人数要求恰好装满，对于体重要求尽量多，一开始没做出来，看了下解题，按照自己的感觉写，然后a了状态转移方程：dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数，j表示背包容量，k表示输入的体重的代码如下： #include<iostream>#include<

阅读更多...

hdu2159（二维背包）

hdu2159（二维背包）

这是我的第一道二维背包题，没想到自己一下子就A了，但是代码写的比较乱，下面的代码是我有重新修改的状态转移：dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示，打了i个怪物，消耗j的耐力值，所得到的最大经验值代码如下： #include<iostream>#include<algorithm>#include<

阅读更多...

csu(背包的变形题)

csu(背包的变形题)

题目链接这是一道背包的变形题目。好题呀题意:给n个怪物，m个人，每个人的魔法消耗和魔法伤害不同，求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

阅读更多...

hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点代码如下： #include<iostream>#include<algorithm

阅读更多...

hdu1171（母函数或多重背包）

hdu1171（母函数或多重背包）

题意：把物品分成两份，使得价值最接近可以用背包，或者是母函数来解，母函数（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v）其中指数为价值，每一项的数目为（该物品数+1）个代码如下： #include<iostream>#include<algorithm>

阅读更多...

动态规划---打家劫舍

动态规划---打家劫舍

题目：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。思路：动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表

阅读更多...

usaco 1.3 Barn Repair（贪心）

usaco 1.3 Barn Repair（贪心）

思路：用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序，选取最大的M-1个作为间隙，其余地方用木板盖住。做法： 1.若，板（M）的数目大于或等于牛棚中有牛的数目（C），则目测给每个牛牛发一个板就为最小的需求~ 2.否则，先对牛牛们的门牌号排序，然后用一个数组 blank[ ] 记录两门牌号之间的距离，然后用数组 an

阅读更多...

hdu 2602 and poj 3624(01背包)

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码： #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

阅读更多...

软考系统规划与管理师考试证书含金量高吗？

软考系统规划与管理师考试证书含金量高吗？

2024年软考系统规划与管理师考试报名时间节点：报名时间：2024年上半年软考将于3月中旬陆续开始报名考试时间：上半年5月25日到28日，下半年11月9日到12日分数线：所有科目成绩均须达到45分以上（包括45分）方可通过考试成绩查询：可在“中国计算机技术职业资格网”上查询软考成绩出成绩时间：预计在11月左右证书领取时间：一般在考试成绩公布后3~4个月，各地领取时间有所不同

阅读更多...

uva 10130 简单背包

uva 10130 简单背包

题意：背包和代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>

阅读更多...