首页 > 代码库 > POJ 1010 STAMPS
POJ 1010 STAMPS
http://poj.org/problem?id=1010
题意:
一: 给定多种类型邮票的面值(不同类型邮票的面值可以相同)
二: 给出客户所需的总面值,求不超过4张邮票的总面值为所给面值的最佳购买方案
最佳方案的定义为: ①种类最多 ②张数最少 ③单张面值最大
若最佳方案多于一个则输出tie
若不存在满足需求的方案,输出none
否则,输出最佳方案
解法:
dfs
主要的几点剪枝:
①每种方案邮票数都不超过4,考虑上tie的情况,则每种面值的邮票只保留5种就够了
②DFS深度不超过4
③邮票按面值升序排序,DFS到面值k时,不再搜索面值<k的邮票
代码: 16MS 352K
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define N 25struct Node { int typ, num, mx, amo[N]; //种类数,张数,最大面值,各种类数量} p, t;int a[N], x, n, ans;void dfs(int num, int val, int crt) { //当前数量,当前总面值,第crt种 if (val == x) { //符合条件 t.typ = t.mx = 0; t.num = num; for (int i = 0; i < n; ++i) { //计算数据 if (t.amo[i]) { ++t.typ; if (t.mx < a[i]) { t.mx = a[i]; } } } if (t.typ > p.typ || t.typ == p.typ && t.num < p.num || t.typ == p.typ && t.num == p.num && t.mx > p.mx) { ans = 1; //得到更佳方案 p = t; } else if (t.typ == p.typ && t.num == p.num && t.mx == p.mx) { ++ans; //方案相同 } return; } for (int i = 0; i < 5; ++i) { //枚举当前种邮票的张数 if (num + i <= 4 && val + i * a[crt] <= x && crt < n) { //剪枝 t.amo[crt] += i; dfs(num + i, val + i * a[crt], crt + 1); t.amo[crt] -= i; } }}int main() { while (~scanf("%d", &x) && x) { for (a[n = 0] = x, n++;;) { scanf("%d", &x); if (!x) { break; } int cnt = 0; for (int i = 0; i < n; ++i) { if (a[i] == x) { ++cnt; } } if (cnt < 5) { //同面值保留5种 a[n++] = x; } } sort(a, a + n); //按面值从小到大排序 while (~scanf("%d", &x) && x) { ans = 0; memset(&t, 0, sizeof(t)); memset(&p, 0, sizeof(p)); dfs(0, 0, 0); printf("%d ", x); if (!ans) { //没有方案 printf("---- none\n"); } else if (ans > 1) { //多于一个最佳方案 printf("(%d): tie\n", p.typ); } else { printf("(%d):", p.typ); for (int i = 0; i < n; ++i) { if (p.amo[i]) { for (int j = 0; j < p.amo[i]; ++j) { printf(" %d", a[i]); } } } printf("\n"); } } } return 0;}
POJ 1010 STAMPS
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。