poj 1010（枚举 dfs）

给你一些邮票的面值，然后给你一些顾客给出的价钱，求出邮票的组合来满足每一位顾客，要求是最多四张邮票，每张可以用多次。

如果这些组合都能满足用户的的需求，那么

1.选种类最多的

2.如果种类相同，选总数最多的

3.如果总数相同，选邮票值组合最大值最大的那一组

4.如果连最大值也相同，那么就是tie

5。如果没有这样的组合，也就是不能用4张以内的邮票满足顾客，那么就是none

输出格式，第一个是总价值，括号里面的是邮票的种类，后面是相应的值。

ps:输入的时候是升序的，输出也是升序的。

注意的地方｛防止重复｝:

View Code

 1 void dfs(int st,int step,int sum)//st表示接下来的邮票从第几个选起
 2 {
 3     if(step>4)
 4         return;
 5     if(sum<0)
 6         return;
 7     if(sum==0)
 8     {
 9         solve(step);
10         none=false;
11     }
12     for(int i=st;i<n;i++)
13     {
14         now[step]=i;
15         dfs(i,step+1,sum-stamp[i]);
16     }
17 }

代码：

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 #define MAXN 60
  9 
 10 int stamp[MAXN];
 11 int now[5];//当前选择的邮票
 12 int ans[5];
 13 int total,stamptype,maxstamp;
 14 int n;
 15 bool tie,none;
 16 
 17 void solve(int step)
 18 {
 19     int tmptotal=step;
 20     int tmptype=0,tmpmax=0;
 21 
 22     bool vis[MAXN];
 23     memset(vis,0,sizeof(vis));
 24     for(int i=0;i<tmptotal;i++)
 25     {
 26         if(!vis[now[i]])
 27         {
 28             vis[now[i]]=1;
 29             tmptype++;
 30         }
 31         if(stamp[now[i]]>tmpmax)
 32             tmpmax=stamp[now[i]];
 33     }
 34     if(total==tmptotal && tmptype==stamptype && maxstamp==tmpmax)
 35     {
 36         tie=true;
 37     }
 38     if(stamptype<tmptype || (stamptype==tmptype && total>tmptotal) ||(stamptype==tmptype && total==tmptotal && maxstamp<tmpmax))
 39     {
 40         tie=false;
 41         stamptype=tmptype;
 42         maxstamp=tmpmax;
 43         total=tmptotal;
 44         for(int i=0;i<tmptotal;i++)
 45             ans[i]=now[i];
 46     }
 47 }
 48 
 49 void dfs(int st,int step,int sum)//st表示接下来的邮票从第几个选起
 50 {
 51     if(step>4)
 52         return;
 53     if(sum<0)
 54         return;
 55     if(sum==0)
 56     {
 57         solve(step);
 58         none=false;
 59     }
 60     for(int i=st;i<n;i++)
 61     {
 62         now[step]=i;
 63         dfs(i,step+1,sum-stamp[i]);
 64     }
 65 }
 66 int main()
 67 {
 68     int x=0;
 69     while(scanf("%d",&x) != EOF)
 70     {
 71         n=0;
 72         while(x)
 73         {
 74             stamp[n++]=x;
 75             scanf("%d",&x);
 76         }
 77         while(scanf("%d",&x))
 78         {
 79             if(x==0) break;
 80             none=true;
 81             tie=false;
 82             total=-1;
 83             stamptype=-1;
 84             maxstamp=-1;
 85             dfs(0,0,x);
 86             if(none)
 87                 printf("%d ---- none\n",x);
 88             else if(tie)
 89                 printf("%d (%d): tie\n",x,stamptype);
 90             else
 91             {
 92                 printf("%d (%d):",x,stamptype);
 93                 //for(int i=0;i<total;i++)
 94                 //    ans[i]=stamp[ans[i]];
 95                 //sort(ans,ans+total);
 96                 for(int i=0;i<total;i++)
 97                     printf(" %d",stamp[ans[i]]);
 98                 printf("\n");
 99             }
100 
101         }
102     }
103 
104     return 0;
105 }