首页 > 试题广场 >

邮票

[编程题]邮票
  • 热度指数：17212 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
某人有8 角的邮票5 张，1 元的邮票4 张，1 元8 角的邮票6 张，用这些邮票中的一张或若干张可以得到多少中不同的邮资？

输入描述:
无


输出描述:
输出一行，表示题目所求。
示例1

输入

无

输出

无
算法知识视频讲解
添加回答
C/C++
fxzero头像 fxzero
本质上是动态规划问题。
思路：如果有新的邮票，那么从就能组合出一种新的邮资，前提是与它组合的邮资能够组合出来（dp不为0），并且这个邮资面额要比他大（比如用10元组合8元，做不到呀！）。
面值为邮票面额的邮资要最后才处理。若一开始就处理了，那么有可能 j-postage[i] 等于它自己，也就是它自己与自己能组合出一个新的邮资，不合理。 
#include <stdio.h>
int main()
{
    int postage[15]={8,8,8,8,8,10,10,10,10,18,18,18,18,18,18};
    int dp[189]={1};                  //组合出来的邮资小于等于188（角）
    int i,j;
    for(i=0;i<15;i++)
    {
        for(j=188;j>=postage[i];j--)
        {
            if(dp[j-postage[i]]!=0)dp[j]=1;
        }
    }
    j=0;
    for(i=8;i<=188;i++)if(dp[i]!=0)j++;           //组合不出来8角以下的
    printf("%d",j);
}


编辑于 2020-03-18 09:51:03 回复(3)
羊嗷嗷头像 羊嗷嗷
#include<stdio.h>
main(){
    int a1,a2,a3,price,flag;
    int pri[200];
    for(int i=0;i<200;i++)pri[i]=0;
    for(a1=0;a1<=5;a1++)
        for(a2=0;a2<=4;a2++)
            for(a3=0;a3<=6;a3++)
                pri[8*a1+10*a2+18*a3]=1;
    for(int i=0;i<200;i++){
        if(pri[i]==1){
            flag++;
        }
    }
    printf("%d",flag);          
}
发表于 2019-03-07 15:54:10 回复(0)
C/C++
YhX.头像 YhX. 
#include<stdio.h>
int main()
{
    int i,j,k,num=0;//张数
    float sum[1000];
    for(i=0;i<=5;i++)
        for(j=0;j<=4;j++)
            for(k=0;k<=6;k++)
    {
        if(i==0&&j==0&&k==0) continue;//0张邮票不参与
        sum[num++]=0.8*i+1*j+1.8*k;
    }
    for(i=0;i<num;i++)//去重
    {
        for(j=i+1;j<num;j++)
            if(sum[i]==sum[j])
            {
                sum[j]=sum[num-1];//把最后一个数拿过来
                num--;j--;//个数减一,在从当前位置开始
            }
    }
    printf("%d",num);
}

发表于 2020-05-10 22:27:02 回复(0)
肚儿和尚头像 肚儿和尚 
#include<iostream>
#include<set>

using namespace std;

int main()
{
	set<int> st;
	for(int i=0;i<=5;i++)
	{
		for(int j=0;j<=4;j++)
		{
			for(int k=0;k<=6;k++)
			{
				if(i==0&&j==0&&k==0)	continue;
				else	st.insert(i*8 + j*10 + k*18);
			}
		}
	}
	cout<<st.size()<<endl;
	return 0;
}

//用set最方便，直接去掉重复的，也不用开辟很大的数组，空间上效率高得多。

发表于 2020-02-15 10:40:40 回复(0)
Java
生活喜提我狗命~头像 生活喜提我狗命~ 
import java.util.HashSet;
import java.util.Set;

public class Main {     public static void main(String[] args) {
   int x=8;
   int y=10;
   int z=18;
   int sum=0;
   HashSet set=new HashSet();
   for(int i=0;i<=5;i++){        for(int j=0;j<=4;j++){            for(int k=0;k<=6;k++){               sum=i*x+j*y+k*z;               set.add(sum);            }        }
   }
   System.out.println(set.size()-1);     }         }     

发表于 2019-05-11 15:29:20 回复(0)
沉睡的力量觉醒了头像 沉睡的力量觉醒了
#include <iostream>
#include <cmath>
int main()
{
    int count = 0;
    float sum = 0;
    float sum_all[1000] = {-1};
    float a[3][2] = {0.8, 5, 1, 4, 1.8, 6};
    for (int i = 0; i <= a[0][1]; i++)
    {
        for (int j = 0; j <= a[1][1]; j++)
        {
            for (int k = 0; k <= a[2][1]; k++)
            {
                sum = a[0][0] * i + a[1][0] * j + a[2][0] * k;
                for (int n = 0; n <= count; n++)
                {
                    if (fabs(sum_all[n] - sum) < 0.00001)
                    {
                        //std::cout << "out" << fabs(sum_all[n] - sum) << std::endl;
                        break;
                    }
                    else if (n == count)
                    {
                        sum_all[count] = sum;
                        // std::cout << sum_all[count] << std::endl;
                        count++;
                        break;
                    }
                }
            }
        }
    }
    std::cout << count-1 << std::endl; //减去初始都为0的那一次
}

发表于 2019-05-05 21:16:21 回复(0)
追影逐梦头像 追影逐梦
#include<cstdio>
int a[200]={0};
int main()
{
    int s=0;
    a[0]=1;//除去三种邮票都没有的情况
    for(int i=0;i<=5;i++)
        for(int j=0;j<=4;j++)
            for(int k=0;k<=6;k++)
            {
                if(a[8*i+10*j+18*k]==0)//此面值的邮票还未出现，则加一
                {
                    a[8*i+10*j+18*k]=1;
                    s++;//计数加一
                }
            }
    printf("%d\n",s);
    return 0;
}
发表于 2019-04-06 15:57:03 回复(0)
度小满内部推荐官头像 度小满内部推荐官 
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include <cctype>
using namespace std;
int num[1000];
int main(){
    int a,b,c;
    int j = 0;
    for(int a = 0;a <= 5;a++)
        for(int b = 0;b <= 4;b++)
            for(int c = 0;c <= 6;c++){
                num[j++] = a*8+b*10+c*18;
            }
    sort(num,num+j);
    int sum = 0;
    for(int i = 1;i < j;i++){
        if(num[i]!=num[i-1])
            sum++;
    }
    cout<<sum;
}

发表于 2019-03-05 09:55:46 回复(1)
Python
东天晨韵头像 东天晨韵
stamp8=5
stamp10=4
stamp18=6

L=[]
for i in range(stamp8+1):
    for j in range(stamp10+1):
        for k in range(stamp18+1):
                L.append(8*i+10*j+18*k)
print(len(set(L))-1)
#去重，再减去i j  k都为0的情况
发表于 2019-02-23 22:28:20 回复(0)
沉默的羔羊201804181810466头像 沉默的羔羊201804181810466
#include <stdio.h>
int main(){
    int i,j,k,h;
    int a1=8,a2=10,a3=18;
    int p[1000],length,price,flag=0;
    for(i=0;i<=1000;i++){
        p[i]=0;
    }
    length=0;
    for( i=0;i<=5;i++){
        for( j=0;j<=4;j++){
            for(k=0;k<=6;k++){
                price=a1*i+a2*j+a3*k;               
                for(h=0;h<=length;h++){
                    if(p[h]==price){
                        flag=1;   
                    }
                }
                if(flag==0){
                    length++;
                    p[length]=price;
                }
                flag=0;
            }
        }
    }
    printf("%d\n",length);
    return 0;
}
发表于 2019-02-19 15:03:13 回复(2)
Java
逍遥任我行头像 逍遥任我行
import java.util.HashSet;

public class Main 
{
    public static void main(String[] args)
    {
         int[] a = {0,8,16,24,32,40};
         int[] b = {0,10,20,30,40};
         int[] c = {0,18,36,54,72,90,108};
         HashSet set = new HashSet();
         for(int i = 0;i < a.length; i++)
         {
             for(int j = 0; j < b.length; j++)
             {
                 for(int k = 0; k < c.length; k++)
                 {
                     int sum = a[i] + b[j] + c[k];
                     set.add(sum);
                 }
             }
         }
         
         System.out.println(set.size() - 1);
    }

}
发表于 2019-03-11 22:15:17 回复(0)
C/C++
算法小屁孩头像 算法小屁孩 
#include<bits/stdc++.h>
int main(){
    int num=0,s[200]={0};
    for(int i=0;i<6;i++)
        for(int j=0;j<5;j++)
            for(int k=0;k<7;k++)
                s[i*8+j*10+k*18]++;
    for(int i=1;i<200;i++)//去掉全零情况
        if(s[i]) num++;
    printf("%d\n",num);
}
编辑于 2019-03-09 10:11:40 回复(13)
C/C++
旬201712151646644头像 旬201712151646644
#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
set<float> s;
int cnt=0;
void conmute1(int n,int m,double a,double b)   //计算只有一种邮票和有两种邮票的情况
{
    int i,j;
    for(i=1;i<=n;i++)   //计算一种邮票
        s.insert(i*a);
    for(i=1;i<=n;i++)//计算两种邮票
        for(j=1;j<=m;j++)
        s.insert(i*a+j*b);
}
void conmute2(int n,int m,int w)//计算含有三种邮票的情况
{
   int i,j,k;
    double a=0.8,b=1.0,c=1.8;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
          for(k=1;k<=w;k++)
           s.insert(i*a+j*b+k*c);
}
int main()
{
    conmute1(5,4,0.8,1.0);//在计算两种邮票的组合情况有三种，总共调用三次
    conmute1(4,6,1.0,1.8);
    conmute1(6,5,1.8,0.8);
    conmute2(5,4,6);//计算三种情况的调用
    int ans=s.size();//集合中的个数就是答案
    cout<<ans<<endl;
    return 0;
} 
解题思路：
1.根据题意，邮票的组合情况有三种，分别是只有一种邮票，只有两种邮票和三种邮票都有的情况。
求解方法就是有几种邮票就有几层循环。
2.利用集合的性质，元素是不会有重复的，所以集合中元素的个数就是答案。
3.看了一下前面大佬的答案，忽然才想到，只要求算出个数的话，可以把小数化为整数，都扩大十倍
是不会有影响的，不同的数也不会变成相同，用小数算的话其实是有风险的，double和float要小
心谨慎地使用，如果元素精度高，在set中会严格按照你开的set的精度来排序，但是如果你输出
的时候精度没有达到那么高就会被四舍五入，那么你会发现set中居然存在两个相同的元素，其实他
们是不同的，后面的小数不同。
这是本人第一次写题解，如果有什么不正确的地方，欢迎大家批评指正。



发表于 2019-02-27 19:43:07 回复(3)
233lawliet头像 233lawliet 
#include <stdio.h>


int main(){
    
    int th[200]={0};
    for(int i=0;i<=5;i++){
        for(int j=0;j<=4;j++){
            for(int k=0; k<=6;k++){
                th[4*i+5*j+9*k]=1;
            }
        }
    }
    int num=0;
    for(int i=0;i<200;i++){
        if(th[i]==1){
            num++;
        }
    }
    printf("%d",num-1);



}
思路：  把每种方案映射到数组中，重复的依旧记作1，统计方案的个数。
发表于 2019-03-17 19:25:54 回复(5)
我不是匠人头像 我不是匠人
用STL库中的set用来统计不同的类型

#include<bits/stdc++.h>
using namespace std;
int main(){
   int t;
    set<int> st;
    for(int i=0;i<=5;i++){
        for(int j=0;j<=4;j++){
            for(int k=0;k<=6;k++){
                if(i==0&&j==0&&k==0) continue; //至少用一张邮票
                t = i*8 + j*10 + k*18;
                st.insert(t);    
            }
        }
    }
    cout<<st.size()<<endl;
    return 0;
}
编辑于 2019-07-30 13:37:32 回复(0)
Java
中南的小菜鸡头像 中南的小菜鸡
//HashSet去掉重复元素，不用判断，set的底层帮我们判断
//最后减一是去掉都为0的情况
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<Integer> set = new HashSet();
        for(int i=0;i<=5;i++){
            for(int j=0;j<=4;j++){
                for(int k=0;k<=6;k++){
                    int sum = i*8+10*j+18*k;
                    set.add(sum);
                }
            }
        }
        System.out.println(set.size()-1);
    }
}

发表于 2019-03-23 23:47:03 回复(0)
C/C++
Dancer_Wu头像 Dancer_Wu
提供动态规划的思路
动态规划0-1背包问题改下 ，求是否有恰好装满容量为1，2，....188的背包的方案 
#include<iostream>
using namespace std;
int dp[189];
void Initial()
{
	for (int i = 0; i < 189; i++)           //初始dp数组 
	{
		if (i == 0) dp[i] = 1;
		else dp[i] = 0;
	}

}
int main()
{
	Initial();
	int a[] = {0,8,8,8,8,8,10,10,10,10,18,18,18,18,18,18};
	for(int i=1;i<16;i++)                 //0-1背包变形
		for (int j = 188; j >= a[i]; j--)
		{
			dp[j] = dp[j] + dp[j - a[i]];  
		}
	int count = 0;
	for (int i = 1; i < 189; i++)        //统计1-188能装满的方案数
		if (dp[i] != 0) count++;
	
	cout << count << endl;
	
}


发表于 2020-03-18 00:07:49 回复(0)
VirgilG72头像 VirgilG72

printf("82");  //(逃 
#include <bits/stdc++.h>
using namespace std;
int main(){
	int i,j,k,a[200]={0},count=0;
	for(i=0;i<=5;i++)
		for(j=0;j<=4;j++)
			for(k=0;k<=6;k++){
				if(a[i*8+j*10+k*18]==0){
					count++;
				a[i*8+j*10+k*18]=1;
				}
				
			}
	cout<<count-1<<endl;
	return 0;
}

发表于 2020-04-07 23:37:57 回复(0)
C++
无问西东gmy头像 无问西东gmy 
#include <iostream>
using namespace std;
#define max 8 * 5 + 10 * 4 + 18 * 6                     //最大邮资数（单位：角）
int main() {
    int count[max + 1] = {0};                           //统计每种邮资可能情况数
    for (int i = 0; i <= 5; i++)
        for (int j = 0; j <= 4; j++)
            for (int k = 0; k <= 6; k++) {
                int value = 8 * i + 10 * j + 18 * k;    //邮资值（单位：角）
                if (value != 0)count[value]++;
            }
    int num = 0;                                        //邮资种数
    for (int i = 1; i <= max; i++)
        if (count[i] > 0)
            num++;                         //邮资值存在，邮资种数增1
    cout << num;
}

发表于 2023-01-17 21:32:10 回复(0)
C++
牛客940172389号头像 牛客940172389号 
#include<iostream>
#include<set>
#define v1 8
#define v2 10
#define v3 18
using namespace std;
int main()
{
   
    set<int> value;
    int len=0;
    for(int i=0;i<=6;i++)//1.8元
    {
        for(int j=0;j<=4;j++)//1元
        {
            for(int k=0;k<=5;k++)//0.8元
            {
                int total=i*v3+j*v2+k*v1;
                value.insert(total);
            }
        }
    }
    cout<<value.size()-1<<endl;
}

发表于 2022-03-20 15:02:52 回复(0)
提交观点

问题信息

动态规划 搜索
上传者：小小
难度：
116条回答 9278浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号