DFS题解 | #最小邮票数#

DFS深度优先搜索解题

这题大多数人应该都是用的dp，我采用了dfs来解题，提供一种思路。

#include<iostream>

using namespace std;

const int maxN = 20;
int v[maxN];//邮票价值
int m;//总值
int n;//邮票数量
int minK;//最小数量
//index为当前搜索的邮票编号，sum为当前搜索的价值和，k为当前搜索结果的邮票数量
void dfs(int index, int sum, int k) {
    //搜索成功
    if (sum == m) {
        if (k < minK) {
            minK = k;
            return;
        }
    }
    //剪枝
    if (index >= n || sum > m)
        return;
    //选择当前邮票
    dfs(index + 1, sum + v[index], k + 1);
    //不选择当前邮票
    dfs(index + 1, sum, k);
}

int main() {
    while (cin >> m >> n) {
        //初始化最小数量为邮票总数
        minK = n;
        for (int i = 0; i < n; ++i) {
            cin >> v[i];
        }
        dfs(0, 0, 0);
        //结果未曾改变，即无解，输出0
        if (minK == n) {
            cout << 0 << endl;
        } else {
            cout << minK << endl;
        }
    }
    return 0;
}