计算机算法分析与设计（15）—贪心算法(虚拟汽车加油问题和最优分解问题)

文章目录

• 一、虚拟汽车加油问题
• • 1.1 问题描述
  • 1.2 思路分析
  • 1.3 代码编写
• 二、最优分解问题
• • 2.1 问题描述
  • 2.2 思路分析
  • 2.3 代码编写

一、虚拟汽车加油问题

1.1 问题描述

 一辆虚拟汽车加满油后可行驶

n

n

n km。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少，计算最少加油次数。

数据输入：

第一行有两个整数n和k，表示汽车加满油后可行驶n km,且路途中有k个加油站。接下来的一行中有k+1个整数，表示第k个加油站与k-1个加油站之间的距离。第0个加油站表示处出发地，汽车已加满油，第k+1个加油站便是目的地。

数据输出：

将计算的最少加油次数输出，如果无法到达目的地，则输出 “No Solution”。

1.2 思路分析

 贪心策略：只要汽车能赶到下一个加油站，就不用加油；否则在当前加油站加满油再出发。

1.3 代码编写

样例输入：

7 7

1 2 3 4 5 1 6 6

样例输出：

4

#include
using namespace std;
 
int main(){
	int n,k;
	cin>>n>>k;
	
	int a[k+1];
	for(int i=0; i<k+1; i++){
		cin>>a[i];
	}
		
	bool f=0;
	int sum=0,gas=n; //gas表示当前的油还可以走多少km
	for(int i=0; i<k+1; i++)
	{
		if(n
			f=1;
		}
		if(gas
			sum++; 
			gas=n;
		}
		gas=gas-a[i];
	}
	
	if(f)
	{
		cout<<"No Solution\n";
	}
	else
	{
		cout<<"最少加油次数："<<sum<<endl;
	}
	return 0;
}

二、最优分解问题

2.1 问题描述

 设

n

n

n 是一个正整数。现在要求将

n

n

n 分解为若干互不相同的自然数的和，且使这些自然数的乘积最大。

数据输入：

输入一个正整数n。

数据输出：

输出计算得出的最大乘积。

2.2 思路分析

 1. 整数的一个性质：若

a

+

b

=

N

(

常数

)

a + b =N(常数)

a+b=N(常数)，则

∣

a

−

b

∣

| a – b |

∣a−b∣ 越小，

a

∗

b

a * b

a∗b 越大。

 2. 分析：

n

n

n 为整数相加之和，常数不变。

（

a

+

b

)

2

=

(

a

−

b

)

2

+

4

a

b

=

n

2

—

>

a

b

=

(

n

2

−

(

a

−

b

)

2

)

/

4

（a+b)^2 = (a-b)^2 +4ab =n^2 —> ab=(n^2 -(a-b)^2)/4

（a+b)2=(a−b)2+4ab=n2—>ab=(n2−(a−b)2)/4；所以若

a

+

b

=

常数

a+b=常数

a+b=常数，则

a

−

b

a-b

a−b 的绝对值越小，

a

b

ab

ab 值越大。

 3. 思路：因为要使乘积最大，所以要尽量分解为相似大小的数。分解时，因数从

2

2

2 开始，每次加

1

1

1，

n

=

n

−

a

[

i

]

n=n-a[i]

n=n−a[i]，保证剩下的数比下一次的数大。

 所以最优分解为从

2

2

2 开始连续的自然数最好，最终分解剩余了一个余数，从分解的最后项依次加

1

1

1 即可（这样乘积中大的数会更大，总的乘积会更大）。

 4. 例如：分解

13

13

13 分解为

2

、

3

、

4

2、3、4

2、3、4，还剩下

4

4

4，不够继续分解的下一个数

5

5

5，就把

4

4

4 依次分配给前面的因子，分配顺序是

4

=

>

3

=

>

2

4 => 3 => 2

4=>3=>2。所以最终结果为

3

、

4

、

6

3、4、6

3、4、6，这就是最大乘积的因子。（分配顺序为从大到小，如果还剩下，就继续分配，直到分完变为

0

0

0 为止）。

2.3 代码编写

样例输入：

10

样例输出：

30

#include
using namespace std;

int main()
{
    int a[100];
    int n,i=1,j;
    int sum=1;     
    cin>>n;
    
    a[0]=2;
    n=n-a[0];
    while(n>a[i-1]) //a[i-1]=2
    {
        a[i]=a[i-1]+1; //第二个因子是3，往后依次...... 
        n=n-a[i];
        i++;
    }
 
    while(n>0) //余数依次减1，加在已分配好的因子上
    {
        for(j=0;j<i;j++)
        {
            a[i-j-1]++; //从最大的数开始加1
            n--;        //余数减1 
            if(n==0)    //若n不等于0，继续执行下一轮分配 
            {
			    break;
			}  
        }
    }
 
    j=0;
    while(j<i) //求最终的乘积
    {
        sum=sum*a[j];
        j++;
    }
    cout<<sum;
    return 0;
}