前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDUOJ-----3591The trouble of Xiaoqian

HDUOJ-----3591The trouble of Xiaoqian

作者头像
Gxjun
发布2018-03-22 11:42:16
5900
发布2018-03-22 11:42:16
举报
文章被收录于专栏:ml

The trouble of Xiaoqian

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1076    Accepted Submission(s): 355

Problem Description

In the country of ALPC , Xiaoqian is a very famous mathematician. She is immersed in calculate, and she want to use the minimum number of coins in every shopping. (The numbers of the shopping include the coins she gave the store and the store backed to her.) And now , Xiaoqian wants to buy T (1 ≤ T ≤ 10,000) cents of supplies. The currency system has N (1 ≤ N ≤ 100) different coins, with values V1, V2, ..., VN (1 ≤ Vi ≤ 120). Xiaoqian is carrying C1 coins of value V1, C2 coins of value V2, ...., and CN coins of value VN (0 ≤ Ci ≤ 10,000). The shopkeeper has an unlimited supply of all the coins, and always makes change in the most efficient manner .But Xiaoqian is a low-pitched girl , she wouldn’t like giving out more than 20000 once.

Input

There are several test cases in the input. Line 1: Two space-separated integers: N and T.  Line 2: N space-separated integers, respectively V1, V2, ..., VN coins (V1, ...VN)  Line 3: N space-separated integers, respectively C1, C2, ..., CN The end of the input is a double 0.

Output

Output one line for each test case like this ”Case X: Y” : X presents the Xth test case and Y presents the minimum number of coins . If it is impossible to pay and receive exact change, output -1.

Sample Input

3 70 5 25 50 5 2 1 0 0

Sample Output

Case 1: 3

 多重背包.

代码:

代码语言:javascript
复制
 1     #include<stdio.h>
 2     #include<string.h>
 3     const int inf=0x3f3f3f3f;
 4     struct node
 5     {
 6         int v,c;
 7     };
 8     node sta[105];
 9     int dp[20010];
10     int dp2[20010];
11     int main()
12     {
13         int n,t,i,j,maxc,cnt=1;   //开始cnt赋值在while里面,娘希匹,错了10+
14         while(scanf("%d%d",&n,&t),n+t)
15         {
16             maxc=-inf;
17      
18             for(i=0;i<n;i++)
19             {
20               scanf("%d",&sta[i].v);
21               if(maxc<sta[i].v)      maxc=sta[i].v;
22             }
23             for(i=0;i<n;i++)
24                 scanf("%d",&sta[i].c);
25             maxc+=t;
26             for(i=1;i<=maxc+1;i++)
27                 dp[i]=inf;
28             dp[0]=0;
29             for(i=0;i<n;i++)
30             {
31                 if(sta[i].v*sta[i].c>=t) /*完全背包*/
32                 {
33                     for(j=sta[i].v ; j<=maxc ;j++)
34                     {
35                         if(dp[j]>dp[j-sta[i].v]+1)
36                             dp[j]=dp[j-sta[i].v]+1;
37                     }
38                 }
39                 else
40                 {
41                     int k=1;
42                     while(sta[i].c>k)
43                     {
44                         for( j=maxc ; j>=sta[i].v*k ; j-- )
45                         {
46                             if(dp[j]>dp[j-sta[i].v*k]+k)
47                                    dp[j]=dp[j-sta[i].v*k]+k;
48                         }
49                         sta[i].c-=k;
50                         k<<=1;
51                     }
52                         for( j=maxc; j>=sta[i].c*sta[i].v ; j-- )
53                         {
54                             if(dp[j]>dp[j-sta[i].v*sta[i].c]+sta[i].c)
55                                 dp[j]=dp[j-sta[i].v*sta[i].c]+sta[i].c;
56                         }
57                 }
58 
59             }
60             for(i=1;i<=maxc+1;i++)
61                 dp2[i]=inf;
62             dp2[0]=0;
63             for(i=0;i<n;i++)
64             {
65                 for(j=sta[i].v ;j<=maxc;j++)
66                 {
67                     if(dp2[j]>dp2[j-sta[i].v]+1)
68                           dp2[j]=dp2[j-sta[i].v]+1 ;
69                 }
70             }
71             int ans=inf;
72             for(i=t;i<=maxc ;i++)
73             {
74                if(ans>dp[i]+dp2[i-t])    ans=dp[i]+dp2[i-t];
75             }
76             if(ans==inf)  printf("Case %d: -1\n",cnt++);
77             else    
78                 printf("Case %d: %d\n",cnt++,ans);
79             
80 
81         }
82         return 0;
83     }

 第二种...

代码语言:javascript
复制
 1 #include<stdio.h>
 2 #include<string.h>
 3 const int inf=0x3f3f3f3f;
 4 struct node
 5 {
 6     int v,c;
 7 };
 8 node sta[105];
 9 int dp[20010];
10 int dp2[20010];
11 int main()
12 {
13     int n,t,i,j,maxc,cnt=1;
14     while(scanf("%d%d",&n,&t),n+t)
15     {
16         maxc=-inf;
17         for(i=0;i<n;i++)
18         {
19           scanf("%d",&sta[i].v);
20           if(maxc<sta[i].v)      maxc=sta[i].v;
21         }
22         for(i=0;i<n;i++)
23             scanf("%d",&sta[i].c);
24         maxc+=t;
25         memset(dp,-1,sizeof(dp[0])*(maxc+1));
26         dp[0]=0;
27         for(i=0;i<n;i++)
28         {
29             if(sta[i].v*sta[i].c>=t) /*完全背包*/
30             {
31                 for(j=sta[i].v ; j<=maxc ;j++)
32                 {
33                     if(dp[j-sta[i].v]!=-1&&(dp[j]==-1||dp[j]>dp[j-sta[i].v]+1))
34                         dp[j]=dp[j-sta[i].v]+1;
35                 }
36             }
37             else
38             {
39                 int k=1;
40                 while(sta[i].c>k)
41                 {
42                     for( j=maxc ; j>=sta[i].v*k ; j-- )
43                     {
44                         if(dp[j-sta[i].v*k]!=-1&&(dp[j]==-1||dp[j]>dp[j-sta[i].v*k]+k))
45                                dp[j]=dp[j-sta[i].v*k]+k;
46                     }
47                     sta[i].c-=k;
48                     k<<=1;
49                 }
50                     for( j=maxc; j>=sta[i].c*sta[i].v ; j-- )
51                     {
52                         if(dp[j-sta[i].v*sta[i].c]!=-1&&(dp[j]==-1||dp[j]>dp[j-sta[i].v*sta[i].c]+sta[i].c))
53                             dp[j]=dp[j-sta[i].v*sta[i].c]+sta[i].c;
54                     }
55             }
56 
57         }
58         memset(dp2,-1,sizeof(dp2[0])*(maxc+1));
59         dp2[0]=0;
60         for(i=0;i<n;i++)
61         {
62             for(j=sta[i].v ;j<=maxc;j++)
63             {
64                 if(dp2[j-sta[i].v]!=-1&&(dp2[j]==-1||dp2[j]<dp2[j-sta[i].v]+1))
65                       dp2[j]=dp2[j-sta[i].v]+1 ;
66             }
67         }
68         int ans=inf;
69         for(i=t;i<=maxc ;i++)
70         {
71             if(dp2[i-t]!=-1&&dp[i]!=-1&&ans>dp[i]+dp2[i-t])
72                 ans=dp[i]+dp2[i-t];
73         }
74         if(ans==inf)  printf("Case %d: -1\n",cnt++);
75         else    
76         { 
77             printf("Case %d: %d\n",cnt++,ans);
78         }
79 
80     }
81     return 0;
82 }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2014-03-09 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • The trouble of Xiaoqian
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档