DP|贪心五例

发表于 更新于 Valine： 本文字数： 5k 估计阅读时长 ≈ 5 分钟
问题背景1
一辆汽车加满油后可以行驶n公里，旅途中有加油站，设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。 测试用例： 7 7 （n k） 1 2 3 4 5 1 6 6（第k个加油站与第k-1个加油站之间的距离，其中第一个代表起点，最后一个代表终点。） 输出： 4（最少加油次数）
解题思路1
  只需要考虑能否到下一个站的情况下还能否到达下下个站，如果可以则在下下个站继续判断是否还可以走，如果不可以情况则是（只能经过一个站，并在那个站加油）又或者是经过两个站不能到达第三个站，则在第二个站进行加油。
代码实现1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>

using namespace std;

int main()
{
    int n;
    int k;
    int a[1001] = { 0 };
    cout << "请输入加满油能跑的距离以及有多少个加油站：" << endl;
    cin >> n >> k;
    cout << "请依次输入两个加油站的距离：" << endl;
    for (int i = 1;i <= k + 1;i++)
        cin >> a[i];
    int s = 0;   //判断接下来路程相加是否大于n
    int c = 0;  //加油次数
    int t = 0;  //标记走过的路程
    for (int i = 0;i <= k + 1;i++)
    {
        s += a[i + 1];
        if (s > n)
        {
            if (a[i + 1] > n)
                break;
            else
            {
                c++;
                s = a[i + 1];
            }
        }
        t += 1;
    }
    if (t == k + 2)
        cout <<"最少加油次数：" << c << endl;
    else
        cout << "错误" << endl;
    return 0;
}

问题背景2
假设1元、2元、5元、10元、20元、50元、100元的纸币分别有3、2、2、1、2、3、5张。现在要用这些钱来支付K元，至少要用多少张纸币？
解题思路2
  用贪心算法的思想很简单。每一次都取尽可能币值大的纸币即可
代码实现2 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# include<iostream>
# include<algorithm>
using namespace std;
const int N = 7;
int Count[N] = { 3,2,2,1,2,3,5 };//每一张纸币的数量
int Value[N] = { 1,2,5,10,20,50,100 };//每一张的面额  
int solve(int money)
{
 int num = 0;
 for (int i = N - 1;i >= 0;i--)
 {
  int c = min(money / Value[i], Count[i]);//每一个所需要的张数
  money = money - c * Value[i];
  num += c;//总张数
 }
 if (money > 0) num = -1;
 return num;
}
int main()
{
 int money;
 cout<<"请输入需要兑换的总金额：" << endl;
 cin >> money;
 int res = solve(money);
 if (res != -1) cout << res << endl;
 else cout << "ERROR" << endl;
}
问题背景3
设你是一个正整数。现在要求将n分解为若干互不相同的自然数之和，且使这些自然数的乘积最大。
解题思路3

（1）对于n<=4 可以验证其分解成几个正整数的和的乘积是小于n的。 （2）对于n>4，能证明其能分解成几个数的和使得乘积不小于n。如果分解成1和n-1，那么对于乘积是没有帮助的；因此假设n分解成a和n-a（2<=a<=n-2），如果a和n-a仍然大于4，那么继续分解直至a,n-a小于等于4.因为每次分解都能使乘积增加，所以最优解必定是最终分解结果，也即分解出的数全是2或3。 （3）把m分拆成若干个互不相等的自然数的和，因数个数越多，乘积越大。为了使因数可数尽可能的多，我们把m分解成从2开始的连续的自然数之和，如果最后又剩余的数，将这个剩余的数优先考虑后面项的情况下平均分给前面的各项。

代码实现3 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# include<stdio.h>
int main(){
 int i,j,k;
 int num;
 int n;
 int result = 1;
 scanf("%d",&num);
 int a[100];
 a[0] = 2;
 num = num - a[0];
 n = 0;
 while(true){
  if(num > a[n]){
   a[n + 1] = a[n] + 1;
   num -= a[n + 1];
   n ++;
  }else{
   break;
  }
 }
 i = n;
 while(num > 0){
  a[i] ++;
  num --;
  i = (n + i) % (n + 1);
 }
 for(i = 0;i < n + 1;i ++){
  result *= a[i];
 }
 printf("the max is %d.",result);
 return 0;
}
问题背景4

给定n位正整数a，去掉其中任意k个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n和k，设计一个算法，找出剩下数字组成的新数最小的删数方案。 输入示例： 178543 输出： 13

解题思路4

题可以使用贪心算法解决。算法流程是先从左到右对数的每个数字遍历，在遍历到第m(0<m<n)个数字时，若第m+1个数字小于第m个数字就删除第m个数字，然后重新遍历删除第m个数字后的新数，直至删除k个数字。

要完成此算法的正确性证明，需要证明本题的最优子结构性质，即证明删除一个数字时，删除第一个递减数字后形成的新数确实是形成新数最小的删数方案。设正整数A由n个数字(a1a2…an)组成，am为第一个递减数字，即am是符合am>am+1条件的所有数字中的m最小的数字。若删除了am的新数Am(a1…am-1am+1…an)不是最小的新数，不妨设存在另一种删数方案即删除ax使得新数Ax<Am,其中Ax=(a1…ax-1ax+1…an)。

当x<m时，由于 am为第一个递减数字，故ax+1>ax,可知Ax-Am=(a1…ax-1ax+1…an)-(a1…ax-1ax…an)>0，即Ax>Am与Ax<Am矛盾。

当x>m时，由于 am am+1为递减数字，故 am>am+1,可知Ax-Am=(a1…am-1am…an)-(a1…am-1am+1…an)>0,即Ax>Am与Ax<Am矛盾。

综上，本题具有最优子结构性质和贪心选择性质。

代码实现4 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


#include<stdio.h>
#include<math.h>
int main(){
 int num,k;
 int n;
 int i,j;
 int temp;
 int m;
 scanf("%d%d",&num,&k);
 n = log10(num) + 1;
 int *a = new int[n];
 int *flag = new int[n];
 for(i = 0;i < n;i ++){
  flag[i] = 1;//设置标志位，1表示没有被使用 
 }
 i = 1;
 temp = num;
 while(i <= n){
  a[n - i] = temp % 10;
  temp /= 10;
  i ++;
 }
 for(i = 0;i < k;i ++){
  j = 0;
  while(flag[j] == 0)
   j ++;
  for(m = j + 1;m < n;m ++){
   if(flag[m] == 1){
    if(a[m] >= a[j]){
     j = m;
    }else{
     break;
    }
   }
  }
  flag[j] = 0;
 } 
 for(i = 0;i < n;i ++){
  if(flag[i] == 1)
   printf("%d",a[i]);
 }
 putchar('\n');
 return 0;
}
问题背景5

给定k个排好序的序列s1,s2,…,sk，用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并两个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需要的总比较次数最少。

解题思路5
贪心算法你得知道你贪的是什么，对于本题，如果要求最多比较次数，每次都应该去找长度最大的两个序列进行合并，最后再把合并完的长度，放进原来的数组或向量中，每次合并都让记录次数的值进行加法就可以。
代码实现5 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
# include<stdio.h>
# define n 4
int min(int *a){
 int b[n];
 int i,j,k;
 int result = 0;
 int count = n;
 int temp;
 for(i = 0;i < n;i ++){
  b[i] = a[i];
 }

 while(count > 1){
  for(i = 0;i < count;i ++){
   for(j = i + 1;j < count;j ++){
    if(b[i] > b[j]){
     temp = b[i];b[i] = b[j];b[j] = temp;
    }
   }
  }
  b[0] = b[1] + b[0];
  result += b[0] - 1;
  for(i = 1;i < count - 1;i ++){
   b[i] = b[i + 1];
  }
  count --;
 }
 return result;
}
int max(int *a){
 int b[n];
 int i,j,k;
 int result = 0;
 int count = n;
 int temp;
 for(i = 0;i < n;i ++){
  b[i] = a[i];
 }

 while(count > 1){
  for(i = 0;i < count;i ++){
   for(j = i + 1;j < count;j ++){
    if(b[i] < b[j]){
     temp = b[i];b[i] = b[j];b[j] = temp;
    }
   }
  }
  b[0] = b[1] + b[0];
  result += b[0] - 1;
  for(i = 1;i < count - 1;i ++){
   b[i] = b[i + 1];
  }
  count --;
 }
 return result;
}
int main()
{
 int a[n] = {5,12,11,2};
 printf("the minimum is %d.",min(a));
 printf("the maximum is %d.",max(a));
 return 0;
}