黑马程序员技术交流社区

标题: 求帮助解决这道题(动态规划) [打印本页]

---

作者: LSL321`    时间: 2016-2-19 17:17
标题: 求帮助解决这道题(动态规划)
问题描述

　　给n个有序整数对ai bi，你需要选择一些整数对 使得所有你选定的数的ai+bi的和最大。并且要求你选定的数对的ai之和非负，bi之和非负。

输入格式

　　输入的第一行为n，数对的个数
　　以下n行每行两个整数 ai bi

输出格式

　　输出你选定的数对的ai+bi之和

样例输入

5
-403 -625
-847 901
-624 -708
-293 413
886 709

样例输出

1715

数据规模和约定

　　1<=n<=100
　　-1000<=ai,bi<=1000

---

作者: oassuperhan    时间: 2016-2-19 20:40
带条件的动态规划，貌似有点难度
给你说下我的大体思路，能不能得到精确解没有证明过，
令Ai=ai的和，Bi=bi的和，si=ai+bi,Si=si的和。
首先将列表中ai和bi同时为负的数字全部剔除。剩下的问题就是如何把问题分解。可以先不考虑题目中Ai>=0,Bi>=0的条件，很容易得到一个最大值的关系式，假设这样子得到的和称为Ji（区别于Si），那么Ji=max{(Ji-1 + si),Ji-1},如果ai+bi》0，那么Ji = (Ji-1 + si)，否则就是Ji-1。需要注意，由于ai，bi可能为负数，得到的结果可能使Ai,Bi<0，那么同样再进行一个精确解的计算Si（满足Ai,Bi大于0的解），怎么获得呢？假如已知Si-1，对于xi,yi,
可以把Si表示为max={(Si-1 + si), (Ji-1+si) , Ji-1 , Si-1}大括号里的值首先进行Ai>=0&&Bi>=0的验证，通过之后再比较大小，最后得到结果。

---

作者: oassuperhan    时间: 2016-2-19 20:46


补充：另外一个要注意的是初始值，也就是J1=s1,   S1=max{s1,0}，上面的Ji的方程有错误，难怪感觉有点不对，Ji=max{(Ji-1 + si), (Si-1 + si), (Ji-1)，(Si-1)},里面的数字不进行Ai和Bi的判断，你试下这样行不行。

一个问题只要得出问题的状态转移方程，就能得到底部向上的动态规划算法，我好多年没有研究算法题目，忘得差不多了，上面的状态转移方程好像有点问题，没有证明过是不是准确，但是大体思路是这样子，你再修改下就OK了

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2