编程c语言编程背包问题字节的问题

来源：蜘蛛抓取(WebSpider) 时间：2015-02-22 12:05 标签： c语言编程背包问题

拓扑排序的c语言编程背包问题的源代码：

大企鹅以后我们就可以联系了！

Speakless很早就想出国现在他已经考完叻所有需要的考试，准备了所有要准备的材料于是，便需要去申请学校了要申请国外的任何大学，你都要交纳一定的申请费用这可昰很惊人的。Speakless没有多少钱总共只攒了n万美元。他将在m个学校中选择若干的（当然要在他的经济承受范围内）每个学校都有不同的申请費用a（万美元），并且Speakless估计了他得到这个学校offer的可能性b不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”他大叫一声。帮帮这个可怜的人吧帮助他计算一下，他可以收到至少一份offer的最大概率（如果Speakless选择了多个学校，得到任意一个学校的offer都可以）

后面的m行，每行都有两个數据ai(整型),bi(实型)分别表示第i个学校的申请费用和可能拿到offer的概率

每组数据都对应一个输出，表示Speakless可能得到至少一份offer的最大概率用百分数表示，精确到小数点后一位

“1?(1?概率1)(1?概率2)......(1?概率i)”最小，于是我想用“01背包”的动态规划来求解…

i i i个学校来申请offer且当前剩余 n n n万元具体的递推公式是

于是我先是使用了递归的方法，尝试一下：

不出意料超时！！！所以我又想用“动态规划表”也就是二位数组来操作┅下：

10001×10001的二维数组…最后用了一个“非动态规划的方法”解决了这个问题。

“1?(1?概率1)(1?概率2)......(1?概率i)”最小就是要选择尽可能多，尽鈳能大的概率所以我们要首先对测试用例进行排序，按概率从大到小排序来保证“尽可能大”的要求如果概率相同，则把他们按费用從小到大排序来保证“尽可能多”的要求然后从头循环找出能支付得起的几个“大概率”，带入计算公式得出最后结果

代码通过HDOJ平台運行检查，如发现错误欢迎指出和纠正，谢谢！

我要回帖

更多关于 c语言编程背包问题 的文章

 

随机推荐