13. 最小邮票数

题目描述

有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。

输入描述:

有多组数据，对于每组数据，首先是要求凑成的邮票总值M，M<100。然后是一个数N，N〈20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列

输出描述:

对于每组数据，能够凑成总值M的最少邮票张数。若无解，输出0。

示例1

输入

10
5
1 3 3 3 4

输出

思路一：枚举暴力求解

首先想到暴力求解，把所有情况都列举出来，选出符合题目要求的最佳情况，暴力求解是一个很靠谱的方法，不会出错，但是时间复杂度会很高。
对于本题来说，暴力求解的难点在于如何把所有情况列举出来，观察到每张邮票只有选或者不选这两种情况，对应 1 或者 0，于是想到了使用二进制，对于 n 张邮票，有 2ⁿ 个可能，如图 1 所示。

图 1

只要将二进制的每个数分别和每张邮票相乘，就能遍历所有情况，选择符合要求的最小的邮票张数，也就是二进制中 1 的个数。由此，代码便就成竹于胸了。

解法一

#include<stdio.h>
#include<math.h>
#include<malloc.h>

int optStamp(int *stamp, int n, int capacity){    //暴力求解
    int x = pow(2, n) - 1;    //遍历邮票需要的最大二进制数对应的十进制数
    int sum = 0;    //邮票值的和
    int min = 20;    //所需最小邮票张数，题目规定邮票张数小于20
    int count = 0;    //记录使用的邮票张数
    int *num = (int *) malloc (sizeof(int) * n);    //用来存二进制的每位数，一共需要 n 位，对应邮票张数
    for(int i = 1; i <= x; i++){    //遍历所有可能的二进制
        int temp = i;    //防止改变 i 的值，用临时变量代替 i
        for(int j = 0; j < n; j++){    //生成二进制的数组 
            num[j] = temp % 2;
            temp = temp / 2;
            if(num[j] == 1)    //记录使用的邮票张数
                count++;
        }
        for(int j = 0; j < n; j++){    //得到邮票值的和 
            sum += stamp[j] * num[j];
        }
        if(sum == capacity){    //选择和背包容量一致的邮票值组合中最小的一个组合 
            if(count < min)
                min = count;
        }
        count = 0; 
        sum = 0;
    }
    free(num);
    if(min != 20)
        return min;
    else    //如果 min 没有改变，则说明没有邮票组合符合要求，返回 0
        return 0;
}

int main(){
    int capacity;    //邮票需要凑成的值
    int n;    //邮票张数
    while(scanf("%d", &capacity) != EOF){
        scanf("%d", &n);
        int *stamp = (int *) malloc (sizeof(int) * n);
        for(int i = 0; i < n; i++)
            scanf("%d", &stamp[i]);
        printf("%d", optStamp(stamp, n, capacity));
        free(stamp);
    }
    return 0;
}

思路二：深度优先

在牛客网讨论区看到了这个方法，用深度优先递归遍历所有邮票组合情况，复杂度很高，但是代码简短，思路值得学习

解法二

#include<stdio.h>
#include<malloc.h>

int *stamp;    //存邮票的数组 
int capacity;    //邮票需要凑成的值 
int min;    //所需最小邮票张数 
int n;    //邮票张数 

void dfsStamp(int index, int add, int count){    //index 控制邮票增加，add 记录邮票总和，count 记录邮票张数 
    if(add == capacity){    //深度优先是先走到最长，然后往回遍历，所以最后一次符合要求的便是最小值 
        min = count;
        return;
    }
    for(int i = index + 1; i < n; i++)
        dfsStamp(i, add + stamp[i], count + 1);
}

int main(){
    while(scanf("%d", &capacity) != EOF){
        scanf("%d", &n);
        stamp = (int *) malloc (sizeof(int) * n);
        for(int i = 0; i < n; i++)
            scanf("%d", &stamp[i]);
        dfsStamp(-1, 0, 0);
        printf("%d", min);
        free(stamp);
    }
    return 0;
}

初看这段代码，不是很能理解这个深度优先遍历的过程，for 循环里面嵌套了一个递归，于是我把递归过程列了出来，如图 2 所示，可以点开图片查看原图。

图 2

思路三：动态规划

把题目抽象化（X₁, X₂, ... , X_n，其中 X_i 取0或1，表示第 i 张邮票选或不选），V_i 表示第 i 张邮票的面值；
即需要求 min{X₁ + X₂ + ... + X_n}
约束条件：X₁V₁ + X₂V₂ + ... + X_nV_n = capacity（capacity 为需要凑成的邮票面值）
定义 dp[i]：数组下标 i 表示需要凑成的值，数组的值表示所需最小邮票张数，则可分为两种情况：
（1）i 不变，则为 dp[i]；
（2）i 退一步，减去一张邮票，则问题转化为求减去一张邮票时的最张数，则为 dp[j] = min(dp[j], dp[j - stamp[i]] + 1)

解法三

#include <stdio.h>
#include <malloc.h>

#define min(a, b) (a < b) ? a : b

int dpStamp(int *stamp, int n, int capacity){
    int dp[101];    //动态规划数组，数组下标表示需要凑成的值，数组的值表示所需最小邮票张数
    dp[0] = 0;    //凑成 0 显然需要 0 张邮票
    for(int i = 1; i < 101; i++)    //初始化 dp 为一个很大的值，题目规定小于 20，20 即可
        dp[i] = 20;
    for(int i = 0; i < n; i++)    //状态转移方程见文章解释
        for(int j = capacity; j >= stamp[i]; j--){    //这里需要倒着遍历，才能保证每张邮票只出现一次
            dp[j] = min(dp[j], dp[j - stamp[i]] + 1);
        }
    if(dp[capacity] == 20)    //如果要求的数组值未改变，说明没有满足的情况，输出 0
        dp[capacity] = 0;
    return dp[capacity];
}

int main(){
    int capacity;    //邮票需要凑成的值
    int n;    //邮票张数
    while(scanf("%d", &capacity) != EOF){
        scanf("%d", &n);
        int *stamp = (int *) malloc (sizeof(int) * n);    //存每张邮票的值
        for(int i = 0; i < n; i++){
            scanf("%d", &stamp[i]);
        }
        printf("%d", dpStamp(stamp, n, capacity));
        free(stamp);
    }
    return 0;
}

图中的 for 循环不太好理解，我把过程写出来了
第一趟循环：
dp[10] = min(dp[10], dp[10 – 1] + 1) = dp[10]
dp[9] = min(dp[9], dp[9 – 1] + 1) = dp[10]
……
dp[2] = min(dp[2], dp[2 – 1] + 1) = dp[2]
dp[1] = min(dp[1], dp[1 – 1] + 1) = 1

第二趟循环：
dp[10] = min(dp[10], dp[10 – 3] + 1) = dp[10]
dp[9] = min(dp[9], dp[9 – 3] + 1) = dp[9]
……
dp[5] = min(dp[5], dp[5 – 3] + 1) = dp[5]
dp[4] = min(dp[4], dp[4 – 3] + 1) = 2
dp[3] = min(dp[3], dp[3 – 3] + 1) = 1

第三趟循环：
dp[10] = min(dp[10], dp[10 – 3] + 1) = dp[10]
dp[9] = min(dp[9], dp[9 – 3] + 1) = dp[10]
……
dp[7] = min(dp[7], dp[7 – 3] + 1) = 3
dp[6] = min(dp[6], dp[6 – 3] + 1) = 2
dp[5] = min(dp[5], dp[5 – 3] + 1) = dp[5]
dp[4] = min(dp[4], dp[4 – 3] + 1) = 2
dp[3] = min(dp[3], dp[3 – 3] + 1) = 1

第四趟循环：
dp[10] = min(dp[10], dp[10 – 3] + 1) = dp[10]
dp[9] = min(dp[9], dp[9 – 3] + 1) = 3
dp[8] = min(dp[8], dp[8 – 3] + 1) = dp[8]
……
dp[4] = min(dp[4], dp[4 – 3] + 1) = 2
dp[3] = min(dp[3], dp[3 – 3] + 1) = 1

第五趟循环：
dp[10] = min(dp[10], dp[10 – 4] + 1) = 3
dp[9] = min(dp[9], dp[9 – 4] + 1) = dp[9]
……

13. 最小邮票数

题目描述

输入描述:

输出描述:

示例1

思路一： 枚举暴力求解

解法一

思路二： 深度优先

解法二

思路三： 动态规划

解法三

推荐阅读更多精彩内容

思路一：枚举暴力求解

思路二：深度优先

思路三：动态规划