首页 > 试题广场 >

邮票

[编程题]邮票

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

某人有8 角的邮票5 张，1 元的邮票4 张，1 元8 角的邮票6 张，用这些邮票中的一张或若干张可以得到多少中不同的邮资？

输入描述:

无

输出描述:

输出一行，表示题目所求。

示例1

输入

无

输出

无

算法知识视频讲解

C/C++

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.

#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

#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

#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

#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

提供动态规划的思路

动态规划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)

虎牙招聘内推官

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

#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++

Zh7481696

贴一个回溯做法：

#include<bits/stdc++.h>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
  private:
    set<int>appeared;
    vector<vector<int>>posts;
    void backtrack(int pos, int sum) {
        if (pos >= 3)return;
        for (int i = 0; i < posts[pos].size(); i++) {
            sum += posts[pos][i];
            if (!appeared.count(sum)) {
                appeared.insert(sum);
            }
            backtrack(pos + 1, sum);
        }
    }

  public:
    int postMoneyKind() {
        posts = {
            {0, 8, 8, 8, 8, 8},
            {0, 10, 10, 10, 10},
            {0, 18, 18, 18, 18, 18, 18}
        };
        backtrack(0, 0);
        return appeared.size();
    }
};
int main() {
    Solution sol;
    cout << sol.postMoneyKind()-1 << endl;
    return 0;
}

发表于 2025-03-21 21:42:17 回复(0)

提交观点

问题信息

动态规划搜索

上传者：小小

难度：

119条回答 68收藏 11381浏览

通过挑战的用户

查看代码

时间会证明。

2022-09-13 19:50:21
微笑诉说悲伤

2022-09-08 23:44:45
Spectre_

2022-08-29 20:47:08
EvenLia...

2022-07-15 15:12:06
牛客35922...

2022-07-02 20:35:23

邮票

输入描述:

输出描述:

输入

输出

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[i8+j10+k18]==0){ count++; a[i8+j10+k18]=1; } } cout<<count-1<<endl; return 0; }

问题信息

热门推荐

通过挑战的用户

相关试题

邮票

输入描述:

输出描述:

输入

输出

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; }

问题信息

热门推荐

通过挑战的用户

相关试题

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[i8+j10+k18]==0){ count++; a[i8+j10+k18]=1; } } cout<<count-1<<endl; return 0; }