课后算法题求解~

时间:2022-03-03 11:16:37
算法题大概的描述如下:
    一个公司要在一条高速路旁建很多旅馆,可供选择的地址共有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


引用 2 楼 limit_clear 的回复:
C/C++ codeint i,p=p1,flag=m1;//p为总利润,flag标记上个旅馆距出发点的距离for(i=2;i<=n;i++)if(mi-flag>=k){p+=pi;flag=mi;}

楼上的做法显然有问题,如果只有两个位置,利润为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);


如果说的不正确的地方请指正,谢谢!

#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 ;

建立旅馆的地点位置,可以通过回溯一次遍历完成。

具体代码就不写了。

#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


引用 2 楼 limit_clear 的回复:
C/C++ codeint i,p=p1,flag=m1;//p为总利润,flag标记上个旅馆距出发点的距离for(i=2;i<=n;i++)if(mi-flag>=k){p+=pi;flag=mi;}

楼上的做法显然有问题,如果只有两个位置,利润为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);


如果说的不正确的地方请指正,谢谢!

#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 ;

建立旅馆的地点位置,可以通过回溯一次遍历完成。

具体代码就不写了。

#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


问题不错,的确是用动态规划