USACO Fence Rails

首先，要弄明白题目的意思，简单说就是有N个背包，每个有一定的重量限制，有R件物品（每件物品都不可分割），每件有一定的重量，求这些背包可以装下的物品的最大数量。题目中有一句话容易引起误解：There is no need to manufacture more rails (or more of any kind of rail) than called for the list of required rails.本人最初认为必须“恰好”把背包装满（NOCOW上的样例解释也是这样的），因此折腾了好长一段时间。实际上没有这个限制。

既然要装下尽可能多的物品，那么就应该先选入小的物品。所以，先把物品按照重量递增排序。那么：
1）如果前k物品不能装入背包，那么即使把其中一个物品P换成k+1~R中的一个物品Q，由于Q的重量大于P，因此也绝对不可能成功装入背包。
2）如果前k个物品可以装入背包，那么前k-1个物品也一定能装入背包。
3）如果前k个物品不能装入背包，那么前k+1个物品也一定不能装入背包。
这样，一个最值问题就转化成了判定性问题，只要枚举出可行的最大k值就可以了。从2、3两个结论中还可以得知可行性与k的关系是“单调”的，因此，可以使用二分查找优化枚举(貌似不二分也可以通过所有数据)。

因此，只要构建一个函数，用来判断前k个物品是否可以装入，程序就完成了一大半。

最朴素的方法(检测第0～index号物品是否可以装入)：

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

01 int dfs_check(int index)
02 {
03     int i;
04     if(index < 0)      //成功装入背包
05         return 1;
06    
07     for(i = 0;i < N;i ++)
08     {
09         if(board[i] >= rail[index])    //把rail[index]放入背包
10         {
11             board[i] -= rail[index];
12             r = dfs_check(index - 1);
13             board[i] += rail[index];
14             if(r == 1)    return 1;   //我们只需要“一个解”，故发现之后立即返回
15         }
16     }
17     return 0;   //放入失败
18 }

可是，这个dfs的速度是非常慢的，因此，需要“剪枝”。为方便起见，记所有背包的容量和为boardsum，前k个物品重量和为railsum[k]。

1）重量大于最大背包容量的物品可以直接删去，容量小于最小物品重量的背包也可以直接删去。（这不算剪枝，应该是预处理）
2）如果可以把前k个物品全部装入，那么浪费掉的容量waste一定是boardsum-railsum[k]。当一个背包的剩余容量小于物品重量的最小值，即不能装入任何物品时，把剩余的容量加到current_waste中，一旦current_waste > waste,就说明这种情况一定不能找到解，应该回溯（比较强大）。
3）如果存在两个物品p1,p2的重量相等，因此可以把他们看作是一样的，所以可以直接固定p2的顺序，把它放在p1后面（非常强大）。
4）如果railsum[k]>boardsum,那么这k个物品一定不能放入背包。
5）改变搜索顺序也可以加快速度，由于放入较大的物品是比较难的，因此dfs的时候可以从大的物品开始。（这点很容易被忘记，但有些时候改变顺序的确很有效）

第1个剪枝是本人自己想到的。2，3，4都是从NOCOW和google上搜到的，真的很难想到，尤其是第三个。

此外，在写二分的时候要小心，不要进入死循环。

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

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 int N,R;
006 int rail[1024];
007 int board[50];
008 int boardsum;
009 int railsum[1024];
010
011 int cmp1(const void *a,const void *b)  //large to small
012 {
013     return(*(int *)a < *(int *)b);
014 }
015
016 int cmp2(const void *a,const void *b)  //small to large
017 {
018     return(*(int *)a > *(int *)b);
019 }
020
021 void init()
022 {
023     scanf("%d",&N);
024     int i;
025     for(i = 0;i < N;i ++)
026     {
027         scanf("%d",&board[i]);
028         boardsum += board[i];
029     }
030     qsort(board,N,sizeof(int),cmp1);
031     scanf("%d\n",&R);
032     for(i = 0;i < R;i ++)
033     {
034         scanf("%d",&rail[i]);
035     }
036     qsort(rail,R,sizeof(int),cmp2);
037     //ignore impossible boards and rails
038     while(rail[R - 1] > board[0] && R > 0)    R --;
039     while(N > 0 && board[N - 1] < rail[0])    N --;
040     if(R == 0 || N == 0)   //无解的特殊情况
041     {
042         printf("0\n");
043         fclose(stdout);
044         exit(0);
045     }
046     railsum[0] = rail[0];
047     for(i = 1;i < R;i ++)
048     {
049         railsum[i] = railsum[i - 1] + rail[i];
050     }
051 }
052
053 int cut_rail_from[1030];
054 int max_waste,cur_waste;
055 int dfs_check(int index)
056 {
057     int start,i,r;
058     if(cur_waste > max_waste)    return 0;
059     if(index < 0)
060     {
061         return 1;
062     }
063     if(rail[index] == rail[index + 1])
064     {
065         start = cut_rail_from[index + 1];
066     }
067     else start = 0;
068    
069     for(i = start;i < N;i ++)
070     {
071         if(board[i] >= rail[index])
072         {
073             board[i] -= rail[index];
074             cut_rail_from[index] = i;
075             if(board[i] < rail[0])    cur_waste += board[i];
076             r = dfs_check(index - 1);
077             if(board[i] < rail[0])    cur_waste -= board[i];
078             board[i] += rail[index];
079             cut_rail_from[index] = -1;
080             if(r == 1)    return 1;
081         }
082     }
083     return 0;
084 }
085
086 void binary()
087 {
088     int i;
089     for(i = 0;i < R;i ++)
090         cut_rail_from[i] = -1;
091     int l,r,mid;
092     l = 0;
093     r = R - 1;
094     for(r = R - 1;r >= 0 && railsum[r] > boardsum;r --);
095     while(l < r)
096     {
097         mid = (l + r + 1) / 2;       //向上取整
098         max_waste = boardsum - railsum[mid];
099         cur_waste = 0;
100         if(dfs_check(mid))
101             l = mid;
102         else    r = mid - 1;
103     }
104     printf("%d\n",l + 1);
105 }
106
107 int main()
108 {
109     freopen("fence8.in","r",stdin);
110     freopen("fence8.out","w",stdout);
111     init();
112     binary();
113     return 0;
114 }