给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤15)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大值MAX,使在1~MAX之间的每一个邮资值都能得到。
例如,N=3,K=2,如果面值分别为1分、4分,则在1分~6分之间的每一个邮资值都能得到(当然还有8分、9分和12分);如果面值分别为1分、3分,则在1分~7分之间的每一个邮资值都能得到。可以验证当N=3,K=2时,7分就是可以得到的连续的邮资最大值,所以MAX=7,面值分别为1分、3分。
输入格式:
2个整数,代表N,K。
输出格式:
2行。第一行若干个数字,表示选择的面值,从小到大排序。
第二行,输出“MAX=S”,S表示最大的面值。
输入样例#1:
3 2
输出样例#1:
1 3
MAX=7
写了个dp,写了个深搜结果慢的和乌龟一样。。
不过幸亏有数据,
思路:深搜枚举,背包DP求值
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 const int MAXN=1001;
7 void read(int & n)
8 {
9 char c='+';int x=0;int flag=0;
10 while(c<'0'||c>'9')
11 { if(c=='-') flag=1; c=getchar(); }
12 while(c>='0'&&c<='9')
13 { x=x*10+(c-48); c=getchar();}
14 flag==1?n=-x:n=x;
15 }
16 int n,k;
17 bool vis[MAXN];
18 int ans[MAXN];// 每一次选的数
19 int dp[MAXN];// 记录每一个数是否有方案可以达到
20 int maxnum;
21 int out[MAXN];
22 int ed=0;
23 inline int pd()
24 {
25 memset(dp,0x3f,sizeof(dp));
26 dp[0]=0;
27 int ok=0;
28 int tot=0;
29 for(int i=1;i<=k;i++)
30 tot=max(ans[i]*n,tot);
31 for(int i=1;i<=k;i++)// 每一种物品
32 for(int j=ans[i];j<=n*ans[i];j++)
33 if(dp[j-ans[i]]+1<=n)
34 dp[j]=min(dp[j],dp[j-ans[i]]+1);
35 for(int i=1;i<=170;i++)
36 {
37 if(dp[i]<888)
38 {
39 ok++;
40 continue;
41 }
42 else break;
43 }
44 return ok;
45 }
46 inline void dfs(int now,int num)// now已经选的数量,num最后一数
47 {
48 ans[now]=num;
49 if(now==k)
50 {
51 int hh=pd();
52 //cout<<hh<<"****"<<endl;
53 if(hh>maxnum)
54 {
55 for(int i=1;i<=k;i++)
56 out[i]=ans[i];
57 //memset(ans,0,sizeof(ans));
58 //cout<<maxnum<<"****"<<endl;
59 maxnum=max(maxnum,hh);
60 ed=max(maxnum,ed);
61 }
62 return ;
63 }
64 for(int i=num+1;i<=51&&i<=n*num+5;i++)
65 {
66 if(vis[i]==0)
67 {
68 vis[i]=1;
69 if(now+1<=k)
70 dfs(now+1,i);
71 vis[i]=0;
72 }
73 else
74 {
75 vis[i]=1;
76 dfs(now,num);
77 vis[i]=0;
78 }
79
80 }
81 }
82 int main()
83 {
84 read(n);read(k);
85 vis[1]=1;
86 dfs(1,1);// 选的第一个数是1,已经选了一个
87 for(int i=1;i<=k;i++)
88 printf("%d ",out[i]);
89 cout<<endl;
90 printf("MAX=%d",ed);
91 return 0;
92 }