USACO Milk Measuring

首先，对输入的pail从小到大排序。
然后，使用DFSID，不断加深搜索深度（即使用pail的个数）。当深度为0时，用动态规划（也就是完全背包算法）检查DFS得到的pail是否可以量出Q的牛奶，如果可以就输出当前使用的pail。

程序的最长运行时间约0.2s。如果在枚举DFS深度时使用二分可以进一步优化。
 

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MAX_LENGTH 10001
05 #define MAX_MILK 20001
06
07 int Q,P;
08 int pail[100];
09 _Bool use[100];
10 _Bool solution[100];
11 int success;
12
13 void init()
14 {
15     static _Bool avail[MAX_LENGTH];
16     memset(avail,0,sizeof(avail));
17     scanf("%d\n%d\n",&Q,&P);
18     int i,t;
19     for(i = 0;i < P;i ++)
20     {
21         scanf("%d\n",&t);
22         avail[t] = 1;
23     }
24     int p;
25     for(p = i = 0;i < MAX_LENGTH;i ++)
26         if(avail[i])    pail[p ++] = i;
27 }
28
29 int try()
30 {
31     static _Bool can[MAX_MILK];   //similar to knapsack problem
32     int i,j;
33     memset(can,0,sizeof(can));
34     can[0] = 1;
35     for(i = 0;i < Q;i ++)
36         if(can[i])
37             for(j = 0;j < P;j ++)
38                 if(use[j] && i + pail[j] <= Q)    can[i + pail[j]] = 1;
39     return (int)can[Q];
40 }
41
42 void dfs(int k,int d)
43 {
44     if(success)    return;
45     if(d == 0)
46     {
47         if(try())
48         {
49             memcpy(solution,use,sizeof(solution));
50             success = 1;
51         }
52         return;
53     }
54     if(k == P)    return;
55     use[k] = 1;
56     dfs(k + 1,d - 1);
57     use[k] = 0;
58     if(k <= P - d)    dfs(k + 1,d);
59 }
60
61 void single()
62 {
63     int i;
64     for(i = 0;i < P;i ++)
65         if(Q % pail[i] == 0)
66         {
67             printf("1 %d\n",pail[i]);
68             fclose(stdout);
69             exit(0);
70         }
71 }
72
73 int main()
74 {
75     int d;
76     freopen("milk4.in","r",stdin);
77     freopen("milk4.out","w",stdout);
78     init();
79     single();   //try if just one pail meets the needs
80     for(d = 2;d <= P;d ++)
81     {
82         success = 0;
83         memset(use,0,sizeof(use));
84         dfs(0,d);
85         if(success)
86         {
87             printf("%d",d);
88             break;
89         }
90     }
91     int i;
92     for(i = 0;i < P;i ++)
93         if(solution[i])    printf(" %d",pail[i]);
94     printf("\n");
95     fclose(stdout);
96     return 0;
97 }