一个公司要在一条高速路旁建很多旅馆,可供选择的地址共有n个,距离起始点的距离可记为m1,m2,m3,...,mn,起始点可记为0,在每个可能的地址i如果建一个旅馆,可以获得利润pi。
现要求每两个旅馆之间的距离至少为k公里,求一算法可求的在高速路旁建了旅馆后可获得的最大利润。
估计各位大侠也遇过类似的题型,可否帮小弟解答一下?给出递推公式或是伪码最好,感激不尽~
11 个解决方案
#1
int i,p=p1,used[n+1]={0},flag=m1;//p为总利润
for(i=2;i<=n;i++)
{
if(mi-flag>=k){p+=pi;flag=mi;}
}
#2
int i,p=p1,flag=m1;//p为总利润,flag标记上个旅馆距出发点的距离
for(i=2;i<=n;i++)
if(mi-flag>=k){p+=pi;flag=mi;}
#3
楼上的做法显然有问题,如果只有两个位置,利润为p1和p2,且p1<p2,并且它们相聚在k内,那结果就应该是p2,你的解法就是p1.
#4
是啊
#5
不知道用递归你能接受不?
递归之前先把所有数据按照距离从小到大排序。
int g_iPMax = 0;//最大效益
int n;//总个数
void Search(int iIndex, int iP, int iDistance)
{
if(iIndex == n + 1)
{//递归结束
if(iP > g_iPMax)
{//记录最大收益
g_iPMax = iP;
}
return;
}
if(iP < 0 || mi - iDistance < k)
{//肯定不建
Search(iIndex + 1, iP, iDistance);
}
else if((n > iIndex && mi - iDistance >= k && mi+1 - mi >= k) ||
(n == iIndex && mi - iDistance >= k))
{//肯定建
Search(iIndex + 1, iP + pi, mi);
}
else
{//不一定建,分两种情况递归
Search(iIndex + 1, iP, iDistance);//不建
Search(iIndex + 1, iP + pi, mi);//建
}
}
调用:
g_iPMax = 0;
Search(0, 0, 0);
如果说的不正确的地方请指正,谢谢!
递归之前先把所有数据按照距离从小到大排序。
int g_iPMax = 0;//最大效益
int n;//总个数
void Search(int iIndex, int iP, int iDistance)
{
if(iIndex == n + 1)
{//递归结束
if(iP > g_iPMax)
{//记录最大收益
g_iPMax = iP;
}
return;
}
if(iP < 0 || mi - iDistance < k)
{//肯定不建
Search(iIndex + 1, iP, iDistance);
}
else if((n > iIndex && mi - iDistance >= k && mi+1 - mi >= k) ||
(n == iIndex && mi - iDistance >= k))
{//肯定建
Search(iIndex + 1, iP + pi, mi);
}
else
{//不一定建,分两种情况递归
Search(iIndex + 1, iP, iDistance);//不建
Search(iIndex + 1, iP + pi, mi);//建
}
}
调用:
g_iPMax = 0;
Search(0, 0, 0);
如果说的不正确的地方请指正,谢谢!
#6
已解决。用动态规划的思想。
#7
#define N 128
int m[N];
float p[N];
double c[N];
int findCandidatePos(int begin, int dist) {
int end = N - 1;
dist += m[begin];
if (m[end] < dist) return N;
int mid = begin;
while (begin < end)
{
mid = (begin + end) / 2;
if (dist < m[mid])
{
end = mid - 1;
}
else if (m[mid] < dist)
{
begin = mid + 1;
}
else
{
break;
}
}
return (m[mid] < dist]) ? mid + 1 : mid;
}
double maxPrice(int curPos, int dist)
{
if (curPos == N) return 0.0;
if (c[curPos] > 0) return c[curPos];
double curMaxPric = 0.0;
int inputCurPos = curPos;
while (curPos < N)
{
int k = findCandidatePos(curPos, dist);
double kMaxPric = 0.0;
while (k < N)
{
double pk = maxPrice(k, dist);
if (pk > kMaxPric)
{
kMaxPric = pk;
}
k = findCandidatePos(k, dist);
}
kMaxPric += p[curPos];
if (kMaxPric > curMaxPric)
{
curMaxPric = kMaxPric;
}
++curPos;
}
c[inputCurPos] = curMaxPric;
return curMaxPric;
}
#8
这种求最优问题通常是用动态规划
#9
这个题目属于动态规划题目,推导公式如下:
假设:f(n)表示 在前n个地点(1~n)中, 第n个地点被确定建立旅馆的时候最大收益值。
那么就有:
f(n) = max( f(i) + pn ) 其中 i = 0,....n-1.并且 mn - mi >= k .
初始条件是:
f(0) = p0 ;
附:pn表示,再第n个位置建立旅馆的收益。mn表示,第n个位置距离起始点的距离。
-------------------
并且最优的建立旅馆的收益是(如果有n个地点):
result(n) = max( f(i) ) 其中i = 0 , .... n ;
建立旅馆的地点位置,可以通过回溯一次遍历完成。
具体代码就不写了。
假设:f(n)表示 在前n个地点(1~n)中, 第n个地点被确定建立旅馆的时候最大收益值。
那么就有:
f(n) = max( f(i) + pn ) 其中 i = 0,....n-1.并且 mn - mi >= k .
初始条件是:
f(0) = p0 ;
附:pn表示,再第n个位置建立旅馆的收益。mn表示,第n个位置距离起始点的距离。
-------------------
并且最优的建立旅馆的收益是(如果有n个地点):
result(n) = max( f(i) ) 其中i = 0 , .... n ;
建立旅馆的地点位置,可以通过回溯一次遍历完成。
具体代码就不写了。
#10
m[n+1]//各点与起点的距离
p[n+1]// 各点利润
d[n+1]//用于存放建旅馆的点
f=0//总利润
pos=0//表示最近刚找到的建旅馆的点
index=0
d[index] = 0
p[0] = 0
for (i = 1; i <= n; i++)
{
//当第i点与前一个 建 旅馆的点的距离大于等于K时,这一点必选
if (m[i] - m[pos] >= k) {
d[++index] = i;
f = f+ p[i];
pos = i;
}
//当第i点与前一个 建 旅馆的点的距离小于K时,则比较此i点与前一个建 旅馆的点谁的 利润大
//建 利润大者
else if (p[i] > p[pos]) {
d[index] = i;
f = f-p[pos] + p[i];
pos = i;
}
#11
问题不错,的确是用动态规划
#1
int i,p=p1,used[n+1]={0},flag=m1;//p为总利润
for(i=2;i<=n;i++)
{
if(mi-flag>=k){p+=pi;flag=mi;}
}
#2
int i,p=p1,flag=m1;//p为总利润,flag标记上个旅馆距出发点的距离
for(i=2;i<=n;i++)
if(mi-flag>=k){p+=pi;flag=mi;}
#3
楼上的做法显然有问题,如果只有两个位置,利润为p1和p2,且p1<p2,并且它们相聚在k内,那结果就应该是p2,你的解法就是p1.
#4
是啊
#5
不知道用递归你能接受不?
递归之前先把所有数据按照距离从小到大排序。
int g_iPMax = 0;//最大效益
int n;//总个数
void Search(int iIndex, int iP, int iDistance)
{
if(iIndex == n + 1)
{//递归结束
if(iP > g_iPMax)
{//记录最大收益
g_iPMax = iP;
}
return;
}
if(iP < 0 || mi - iDistance < k)
{//肯定不建
Search(iIndex + 1, iP, iDistance);
}
else if((n > iIndex && mi - iDistance >= k && mi+1 - mi >= k) ||
(n == iIndex && mi - iDistance >= k))
{//肯定建
Search(iIndex + 1, iP + pi, mi);
}
else
{//不一定建,分两种情况递归
Search(iIndex + 1, iP, iDistance);//不建
Search(iIndex + 1, iP + pi, mi);//建
}
}
调用:
g_iPMax = 0;
Search(0, 0, 0);
如果说的不正确的地方请指正,谢谢!
递归之前先把所有数据按照距离从小到大排序。
int g_iPMax = 0;//最大效益
int n;//总个数
void Search(int iIndex, int iP, int iDistance)
{
if(iIndex == n + 1)
{//递归结束
if(iP > g_iPMax)
{//记录最大收益
g_iPMax = iP;
}
return;
}
if(iP < 0 || mi - iDistance < k)
{//肯定不建
Search(iIndex + 1, iP, iDistance);
}
else if((n > iIndex && mi - iDistance >= k && mi+1 - mi >= k) ||
(n == iIndex && mi - iDistance >= k))
{//肯定建
Search(iIndex + 1, iP + pi, mi);
}
else
{//不一定建,分两种情况递归
Search(iIndex + 1, iP, iDistance);//不建
Search(iIndex + 1, iP + pi, mi);//建
}
}
调用:
g_iPMax = 0;
Search(0, 0, 0);
如果说的不正确的地方请指正,谢谢!
#6
已解决。用动态规划的思想。
#7
#define N 128
int m[N];
float p[N];
double c[N];
int findCandidatePos(int begin, int dist) {
int end = N - 1;
dist += m[begin];
if (m[end] < dist) return N;
int mid = begin;
while (begin < end)
{
mid = (begin + end) / 2;
if (dist < m[mid])
{
end = mid - 1;
}
else if (m[mid] < dist)
{
begin = mid + 1;
}
else
{
break;
}
}
return (m[mid] < dist]) ? mid + 1 : mid;
}
double maxPrice(int curPos, int dist)
{
if (curPos == N) return 0.0;
if (c[curPos] > 0) return c[curPos];
double curMaxPric = 0.0;
int inputCurPos = curPos;
while (curPos < N)
{
int k = findCandidatePos(curPos, dist);
double kMaxPric = 0.0;
while (k < N)
{
double pk = maxPrice(k, dist);
if (pk > kMaxPric)
{
kMaxPric = pk;
}
k = findCandidatePos(k, dist);
}
kMaxPric += p[curPos];
if (kMaxPric > curMaxPric)
{
curMaxPric = kMaxPric;
}
++curPos;
}
c[inputCurPos] = curMaxPric;
return curMaxPric;
}
#8
这种求最优问题通常是用动态规划
#9
这个题目属于动态规划题目,推导公式如下:
假设:f(n)表示 在前n个地点(1~n)中, 第n个地点被确定建立旅馆的时候最大收益值。
那么就有:
f(n) = max( f(i) + pn ) 其中 i = 0,....n-1.并且 mn - mi >= k .
初始条件是:
f(0) = p0 ;
附:pn表示,再第n个位置建立旅馆的收益。mn表示,第n个位置距离起始点的距离。
-------------------
并且最优的建立旅馆的收益是(如果有n个地点):
result(n) = max( f(i) ) 其中i = 0 , .... n ;
建立旅馆的地点位置,可以通过回溯一次遍历完成。
具体代码就不写了。
假设:f(n)表示 在前n个地点(1~n)中, 第n个地点被确定建立旅馆的时候最大收益值。
那么就有:
f(n) = max( f(i) + pn ) 其中 i = 0,....n-1.并且 mn - mi >= k .
初始条件是:
f(0) = p0 ;
附:pn表示,再第n个位置建立旅馆的收益。mn表示,第n个位置距离起始点的距离。
-------------------
并且最优的建立旅馆的收益是(如果有n个地点):
result(n) = max( f(i) ) 其中i = 0 , .... n ;
建立旅馆的地点位置,可以通过回溯一次遍历完成。
具体代码就不写了。
#10
m[n+1]//各点与起点的距离
p[n+1]// 各点利润
d[n+1]//用于存放建旅馆的点
f=0//总利润
pos=0//表示最近刚找到的建旅馆的点
index=0
d[index] = 0
p[0] = 0
for (i = 1; i <= n; i++)
{
//当第i点与前一个 建 旅馆的点的距离大于等于K时,这一点必选
if (m[i] - m[pos] >= k) {
d[++index] = i;
f = f+ p[i];
pos = i;
}
//当第i点与前一个 建 旅馆的点的距离小于K时,则比较此i点与前一个建 旅馆的点谁的 利润大
//建 利润大者
else if (p[i] > p[pos]) {
d[index] = i;
f = f-p[pos] + p[i];
pos = i;
}
#11
问题不错,的确是用动态规划