最小邮票数（九度1209）

约定不等于承诺〃 2022-08-07 15:51 115阅读 0赞

据说是清华07年的研究生复试机试题，类似01背包，动态规划一直不太会，这道题不难，刚好可以练练手。

**题目描述：**  
有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。  
如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。  
**输入：**  
有多组数据，对于每组数据，首先是要求凑成的邮票总值M，M<100。然后是一个数N，N〈20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列。  
**输出：**  
对于每组数据，能够凑成总值M的最少邮票张数。若无解，输出0。  
**样例输入：**  
10  
5  
1 3 3 3 4  
**样例输出：**  
3

**代码：**

#include <iostream>
    using namespace std;
    //N < 20
    //M <100
    //dp[i,j]=min(dp[i-1,j-var[i]]+1,dp[i-1,j]);
    #define INFINITY 999
    int var[1001];
    int dp[1001][1001];
    int N;
    int M;
    int main()
    {
    	while(cin>>M>>N)
    	{
    		for(int i = 1;i <= N; i++)
    		{
    			cin >> var[i];
    		}
    		for(int i = 1;i<=M;i++)
    		{
    			dp[0][i]=INFINITY;
    		}
    		for(int i= 0;i<=N;i++)
    		{
    			dp[i][0]=0;
    		}
    		int j;
    		int i;
    		for(i=1;i<=N;i++)
    		{
    			for(j=1;j<=M;j++)
    			{
    				if(j>=var[i])
    				{
    					dp[i][j]=min(dp[i-1][j-var[i]]+1,dp[i-1][j]);
    				}
    				else
    					dp[i][j]=dp[i-1][j];
    			}
    		}
    		if(dp[N][M] != INFINITY)
    			cout<<dp[N][M]<<endl;
    		else
    			cout<<"0"<<endl;
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，115人围观）

还没有评论，来说两句吧...

相关阅读

相关细数九种常见的设计模式

在软件工程中，设计模式（Design Pattern）是对软件设计中普遍存在（反复出现）的各种问题，所提出的解决方案。根据模式的目的来划分的话，GoF（Gang of Four

拼搏现实的明天。/ 2022年12月15日 14:25/ 0 赞/ 153 阅读

相关数据结构堆的时间复杂度(最大堆，最小堆)

创建堆的方式有两种，一种是一边插入结点，一边调用堆的插入方法调整堆，这样的时间复杂度就是 O(NlogN)，而第二种方式就把时间复杂度缩减到了O(N)，它是采用先把结点插入

妖狐艹你老母/ 2022年11月07日 11:40/ 0 赞/ 189 阅读

相关【九度1502】最大值最小化

题目1502：最大值最小化时间限制：1 秒内存限制：128 兆特殊判题：否提交：566 解决：214 题目描述：在印刷术发明之前，复制一本书是一个很困难

淡淡的烟草味﹌/ 2022年09月25日 08:29/ 0 赞/ 143 阅读

相关最小邮票数（九度1209）

据说是清华07年的研究生复试机试题，类似01背包，动态规划一直不太会，这道题不难，刚好可以练练手。题目描述：有若干张邮票，要求从中选取最少的邮票张数凑成一个

约定不等于承诺〃/ 2022年08月07日 15:51/ 0 赞/ 116 阅读

相关蓝桥杯-剪邮票

剪邮票如【图1.jpg】, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连）比如，【图2.jpg】，

刺骨的言语ヽ痛彻心扉/ 2022年06月18日 10:16/ 0 赞/ 146 阅读

相关有4种面值的邮票很多枚，这4种邮票面值分别1, 4, 12, 21，取5张求取出这些邮票的最大连续组合值。

//有4种面值的邮票很多枚，这4种邮票面值分别1, 4, 12, 21，取5张求取出这些邮票的最大连续组合值。 include <stdio.h>

雨点打透心脏的1/2处/ 2022年05月22日 08:28/ 0 赞/ 103 阅读

相关 1209 最大面积

1209: 最大面积给定一个n\m的矩阵，其中有k个格子是1，其他全部是0。你的任务是告诉我最大的全部由1组成的图形的最大面积为多少？ Input 输入包括多组

╰半夏微凉°/ 2022年05月15日 04:15/ 0 赞/ 164 阅读

相关 DLUTOJ 1209 字典序和r-子集

[ 传送门][Link 1] Time Limit: 6 Sec Memory Limit: 128 MB Submit: 73 Solved: 14 Desc

傷城~/ 2021年12月05日 15:07/ 0 赞/ 180 阅读

相关民居邮票与实景民居

小时候常见到的邮票就是这些民居邮票，8分钱，现在也有这些邮票只是面值翻了N倍。呵呵。我们一起来看一下这些民居邮票和实景民居的对比吧。上海民居 ![tqiw\_2

骑猪看日落/ 2021年11月11日 22:58/ 0 赞/ 259 阅读

相关 BZOJ 1426: 收集邮票

1426: 收集邮票 Time Limit: 1 Sec Memory Limit: 162 MB Submit: 315 Solved: 251 \[[Su

你的名字/ 2021年10月26日 12:16/ 0 赞/ 234 阅读