最小邮票数

[编程题]最小邮票数

热度指数：29714 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。如，有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

输出

算法知识视频讲解

philos

发表于 2021-02-04 16:53:21

思路最简单的方法就是深搜了，就是逆序选择每一次可能选择的邮票。 #include<iostream> #include<vector> using namespace std; int getCnt(int m, vector<int>& stamp 展开全文

铁锅炖大大鹅

发表于 2022-03-16 16:49:55

DFS深度优先搜索解题这题大多数人应该都是用的dp，我采用了dfs来解题，提供一种思路。 #include<iostream> using namespace std; const int maxN = 20; int v[maxN];//邮票价值 int m;//总值 int n 展开全文

周威zq

发表于 2021-02-20 17:20:09

#include<iostream> #include<cstdio> using namespace std; const int maxn=100; int weight[maxn]; int dp[maxn]; //每张邮票价值为1，求背包容量M,N个物品，装满展开全文

健康快乐最重要

发表于 2020-03-01 14:04:57

背包+回溯1.第一种方法没有优化2.第二种方法是空间优化的 #include<iostream> #include<algorithm> using namespace std; struct goods{ int v; int w; }g[20]; bool 展开全文

zzhbrother

发表于 2021-05-30 14:42:47

// dp[i][j]表示只用前i种邮票能凑成总值M的最少邮票数，如果凑不成为INF // dp[0][j] = INF // dp[i][0] = 0 /* dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - p[i]] + 1) */ #includ 展开全文

ImSev7en_1

发表于 2022-09-11 21:14:52

与0/1背包问题类似： #include <iostream> #include <vector> #define MAXM 101 #define MAXN 21 #define MAX 9 展开全文

flyflyfly00

发表于 2021-04-23 17:12:00

用动态规划，每次从大数开始更新。 #include <iostream> #include<cstring> #define INF 1005 using namespace std; const int N = 21; const int M = 101; int s 展开全文

牛客875497457号

发表于 2022-03-08 10:40:53

最小邮票数的思想是：当前需要凑j块钱，选择了面额为a[i]的邮票，那么可以有两个选择第一：仍然保持dp[j]张数量不变；第二：选择面额为j-a[i]与面额为a[i]的邮票，其有票数为两者之和，即为dp[j-a[i]] + 1; 寻找最优解，即选择两者的最小值。由动态规划的思想，从面值大的往展开全文

华科不平凡

发表于 2020-08-27 11:54:57

首先，这是一个背包问题。描述转化为“背包”，有N个物品，每个物品的质量为Vi，背包重量为M，求最少取多少个物品才能刚好装满背包，如果无法满足条件，返回0。我们用INT32_MAX表示无法凑齐，设dp[i][j]为邮票为前i张时，刚好凑成j所需要的最小邮票张数，有以下状态公式：当j-v[i-1] 展开全文