[搜索]USACO Oct09 Bessie體重問題 diet 解題報告

【問題描述】
Bessie像她的諸多姊妹一樣，因爲從Farmer John的草地吃了太多美味的草而長出了太多的

贅肉。所以FJ將她置於一個及其嚴格的節食計畫之中。她每天不能吃多過H (5 <= H <=

45,000)公斤的乾草。

Bessie只能吃一整捆乾草；當她開始吃一捆乾草的之後就再也停不下來了。她有一個完整的

N (1 <= N <= 500)捆可以給她當作晚餐的乾草的清單。她自然想要儘量吃到更多的乾草。

很自然地，每捆乾草只能被吃一次（即使在列表中相同的重量可能出現2次，但是這表示的是

兩捆乾草，其中每捆乾草最多只能被吃掉一次）。

給定一個列表表示每捆乾草的重量S_i (1 <= S_i <= H), 求Bessie不超過節食的限制的

樣例輸入 (文件 diet.in):

56 4

15

19

20

21

輸入細節:

有四捆草，重量分別是15, 19, 20和21。Bessie在56公斤的限制範圍內想要吃多少就可

以吃多少。

輸出格式:

* 第一行: 一個單獨的整數表示Bessie在限制範圍內最多可以吃多少公斤的乾草。

樣例輸出 (文件 diet.out):

56

輸出細節:

Bessie可以吃3捆乾草（重量分別爲15, 20, 21）。恰好達到她的56公斤的限制。

【分析】

學過OI的人都能看出來，這是一個簡單的搜索題目，由於數據不大，廣度優先搜索即可快速過全數據，無需太多優化。

由於每捆乾草只能用一次，所以有人想在廣搜隊列中開一個bool 數組，用來記錄哪些乾草被吃過了。但是，這樣時間複雜度、空間複雜度都會大大增加，有超時、超出內存限制的風險。

其實，我們可以這樣做防止重複。在隊列中記錄上一次吃的是哪一捆乾草，然後下一次搜索時只需要從上一次乾草的後面開始搜索即可，即吃的乾草的編號構成上升序列，這樣不僅能保證不重複，還能提高程序運行效率。

【我的代碼】

 #include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int W[501];
int L;
int N;
int M=0;

void init()
{
    scanf("%d %d\n",&L,&N);
    for (int i=1;i<=N;i++)
        scanf("%d\n",&W[i]);
}

class QUEUE
{
public:
    int cur;//當前捆的標號
    int now;//當前草的重量   
}Q[1000000];

void bfs()
{
    int big=1;
    int sma=0;
    Q[0].cur=0;
    Q[0].now=0;
    int Tc,Tn;
    while(sma<=big)
    {
        Tc=Q[sma].cur;
        Tn=Q[sma].now;
        for (int i=Tc+1;i<=N;i++)
        {
            if(W[i]+Tn>L)
            {
                if(Tn>M)
                    M=Tn;
                continue;
            }
            if(W[i]+Tn==L)
            {
                M=L;
                return;
            }
            Q[big].cur=i;
            Q[big].now=W[i]+Tn;
            big++;
        }
        sma++;
    }
    return;
}

int main()
{
    freopen("diet.in","r",stdin);
    freopen("diet.out","w",stdout);
    init();
    bfs();
    printf("%d\n",M);
    return 0;
}