牛客网考研机试题集合：邮票

本文主要是介绍牛客网考研机试题集合：邮票，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

方法一：

枚举

#include<bits/stdc++.h>
using namespace std;
const int MAXSIZE=10000;int main() {set<int> s;for(int i=0; i<=5; i++) {for(int j=0; j<=4; j++) {for(int k=0; k<=6; k++) {s.insert(k*18+j*10+8*i);}}}cout<<s.size()-1<<endl;return 0;
}

如果 set<double> s;s.insert(k*1.8+j*1.0+0.8*i)

输出的s.size()==113不知道为什么？

#include<bits/stdc++.h>
using namespace std;
const int MAXSIZE=10000;int main() {set<double> s;for(int i=0; i<=5; i++) {for(int j=0; j<=4; j++) {for(int k=0; k<=6; k++) {double t=k*1.8+j*1.0+0.8*i;s.insert(t);}}}for(auto it=s.begin(); it!=s.end(); it++) {cout<<*it<<endl;}cout<<s.size()-1<<endl;return 0;
}

部分运行结果截图：

方法二：动态规划

0~1完全背包问题：

背包的体积1~188(邮票的总价值）

物体的体积：邮票的面值

物体的价值：0

#include<bits/stdc++.h>
using namespace std;
const int MAXSIZE=10000;
int dp[189];
int main() {fill(dp,dp+189,INT_MIN);dp[0]=0;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] =max(dp[j],dp[j-a[i]]);}int count = 0;for (int i = 1; i < 189; i++)        //ͳ¼Æ1-188ÄÜ×°ÂúµÄ·½°¸Êýif (dp[i] != INT_MIN) count++;cout << count << endl;return 0;
}

 

这篇关于牛客网考研机试题集合：邮票的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---