1月 29, 2009

【解題】錄製專輯 - Record

@
台北市96學年度高中資訊學科能力競賽 - 錄製專輯 (Record)


問題描述

  Jolin是個愛唱歌的小孩,每次總喜歡邊唱邊用電腦把自己的歌聲錄下來,因此長久下來,在她的電腦裡,已儲存了為數不小的個人歌唱作品。由於耶誕節快要到了,為了準備一份特別的耶誕禮物給爸爸,Jolin準備從電腦中儲存的個人歌唱作品,挑選幾首歌製成一張個人專輯CD。由於每張CD的容量有限,而Jolin的個人歌唱作品早已遠遠超過一張CD可收錄的容量,因此Jolin希望你可以幫她想辦法,讓她所製作的專輯中,能有數目最多的歌曲(請注意:每一首歌只能被收錄一次),同時必需剛好裝滿整張CD,不留下任何未使用的空間。


輸入檔格式(C:\record\input.txt)

  輸入檔中的第一行為一個正整數N,代表Jolin的個人歌唱作品數目。第二行則有N個以空白相間隔的正整數Xi,分別代表第i首個人歌唱作品的大小(單位為MBytes)。第三行則有一個正整數S,代表CD的容量(單位為MBytes)。

  為簡化計算過程起見,我們假設每一首歌唱作品的大小皆不相同,同時N≦100,Xi≦200,S≦10000。


輸出檔格式 (C:\record\output.txt)

  請根據輸入檔的資料,在輸出檔中依序印出兩個正整數L與K。其中,L代表最多可以在CD中收錄的歌曲數目,K代表共有幾種方式可以收錄L首歌曲於CD中。注意,若歌曲曲目相同,但排列順序不同,仍視為不同的收錄方式。

  若沒有任何方法可以錄滿整片CD,則L=K=0。


輸入檔範例1

5
10 50 30 70 60
80


輸出檔範例1

2 4


輸入檔範例2

5
10 50 30 70 60
20


輸出檔範例2

0 0


解題思考

  對於這一題,我們首先需要得知,哪些歌加起來可以剛好裝滿整張CD。接著,由於歌曲順序不同仍視為不同的收錄法,因此假設n首歌剛好可以裝滿整張CD,就會有n!種收錄方式。

  所以,現在的問題就在於:該如何得知,哪幾首歌剛好可以裝滿整張CD呢?根據建議,這裡提供一張圖做參考:



  我的作法是,以迴圈搭配遞迴的方式選歌。假設現在取到第一首歌,容量是30。接著,再藉由遞迴的方式選第二首歌。由於第二首歌的大小為60,兩首歌的總容量超過CD大小,因此第二首歌並不能列入CD當中。以此類推,直到抓到最後一首歌,或是CD容量已滿為止。

  或許你會注意到,除了CD剩餘容量外,參考圖片中還有一個"歌曲剩餘"的大小。這個數值代表的意義是:還沒被判斷是否可以放入CD的歌曲總容量(即圖片中未圈選及劃叉的歌曲)。

  記錄這個數字做什麼呢?因為只要這個數字小於CD的剩餘容量,就算這些歌全都收錄在CD中,也不會到題目要求的"剛好裝滿"CD。因此,只要歌曲剩餘大小小於CD剩餘大小,就代表目前的選擇並不可行。

  只要掌握這些概念,程式應該就能夠輕易的實現了。


  結果答案完全是錯的。


  這一題用這種方式來作,若是測試資料的 n 過大,將會導致執行結果超時。因此,勢必要使用別的方式來解才行。 (感謝網友 大丁丁 指正)

  其實,這樣的題型就是所謂的背包問題(knapsack problem)。若是要解出這種題型,比較高效率的方法是利用動態規劃(dynamic programming)

  首先,先要得出一套「公式」,來求得只在前 i 首歌中做選擇,且恰好能裝滿容量為 v 的專輯的最大歌曲數。我們將之設為 f(i, v)。其中,若是我們選了第 i 首歌,則 f(i, v) 將可以看作 f(i - 1, v - x[i]) + 1。也就是「只在前 i - 1 首歌中做選擇,且恰好能裝滿容量為 v - x[i] (因為 x[i] 的空間被第 i 首歌佔據了)的專輯的最大歌曲數加一(第 i 首歌本身)」。

  而若是我們不選第 i 首歌,則 f(i, v) 將可以看作 f(i - 1, v)。也就是「只在前 i - 1 首歌中做選擇,且恰好能裝滿容量為 v (因為不選第 i 首歌)的專輯的最大歌曲數」。如此,便可以得出 f(i, v) = maximum(f(i - 1, v - x[i]) + 1, f(i - 1, v))

  再加上定義出 f(0, 0) = 0 (因為 0 首歌裝滿容量為 0 的專輯能裝的最大歌曲數也為 0 首),且 f(0, v) = -∞ (選 0 首歌裝滿容量大於 0 的專輯的情況必不可能出現),再搭配迴圈就能得到正確的結果了。


  那麼,要如何在不考慮順序情況下,得出的最大歌曲組合數量呢?

  同樣的,若我們設 g(i, v) 為「只在前 i 首歌中做選擇,且恰好能裝滿容量為 v 的專輯的最大歌曲組合數」,再循著類似的原理累加,便可以得出結果。最後,以 g(i, v) 作為係數,乘以 f(i, v) 階層,就是包含各種不同順序的最大歌曲組合數量了。


  還有要注意的一點是,計算出來的結果數字會相當大(畢竟牽扯到階層),所以要用大數來存。這邊允許我偷個懶,直接用我以前寫的大數類別吧。


  其實,這題我還很蠢的把題目的「最大裝滿專輯的歌曲組合數量」,誤解成「能裝滿專輯的歌曲組合數量」,大大的把題目給複雜化了。結果我好不容易寫出來之後,才發現跟大丁丁那弄來的 AC code 跑出的結果有那麼「一點點」不一樣。經過如此改正之後,這題我才算真正解出來。


參考解答(C++)

#include <iostream>
#include <fstream>

#include "include/Large.h"

using namespace std;

int main(void)
{
    ifstream in("C:/record/input.txt");
    ofstream out("C:/record/output.txt", ios_base::trunc);

    cout << "讀入資料 . . ." << endl;

    int n;
    in >> n;
    cout << n << endl;

    int *x = new int[n];
    for (int i = 0; i < n; i++)
    {
        in >> x[i];
        cout << x[i] << " ";
    }

    int s;
    in >> s;
    cout << endl << s << endl;

    in.close();

    int *dp = new int[s + 1];
    dp[0] = 0;
    memset(dp + 1, 0xFF, sizeof(int) * s);

    large *g = new large[s + 1];
    g[0] = 1;

    // dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + 1)
    for (int i = 0; i < n; i++)
    {
        for (int j = s; j >= x[i]; j--)
        {
            if (dp[j - x[i]] >= 0)
            {
                // 找到比當前最多歌曲組合更多歌曲的組合
                if (dp[j - x[i]] + 1 > dp[j])
                {
                    dp[j] = dp[j - x[i]] + 1;
                    g[j] = g[j - x[i]];
                }
                else if (dp[j - x[i]] + 1 == dp[j])
                {
                    // 累加最多歌曲組合的數量
                    g[j] += g[j - x[i]];
                }
            }
        }
    }

    // 計算順序不同的組合
    large number = g[s];
    for (int i = 2; i <= dp[s]; i++)
    {
        number *= i;
    }

    if (dp[s] < 0) { dp[s] = 0; }

    // 輸出得到的結果
    out << dp[s] << " " << number << endl;
    out.close();

    cout << endl << dp[s] << " " << number << endl;
    cout << "輸出資料在 ouput.txt" << endl;

    delete [] x;
    delete [] dp;
    delete [] g;

    system("pause");
}

10 回覆:

匿名 提到...

確定不會超時嗎?

匿名 提到...

我那時候就是用這個方法
結果5組測資只對1組= ="

匿名 提到...

原因是超時

小參 提到...

唔....實測過確實會超時
我想這問題大概被我忽略了Orz

由於手邊沒有當時的測資
所以要確定一定是"解"會比較困難

我會修正之後再貼出來
感謝指正<(_ _)>

匿名 提到...

這裡可以測
http://cat.nknush.kh.edu.tw/ZeroJudge/ShowProblem?problemid=b126

今年有打算參賽嗎XD?

小參 提到...

我連 ZeroJudge 系統有都不知道
真是太不專業了XD

至於比賽....
來不及了, 大學生了Orz
其實我還有點想留級參賽的~哈哈

話說, 留個聯絡管道吧?
一直匿名讓我頗好奇的耶XD

匿名 提到...

MSN: safestation@hotmail.com

shik 提到...

樓上好阿 XD

這題我在ZeroJudge WA掉了 Q_Q

kgame 智涵 提到...

我的答案
http://kgame.ihost.tw/NETCF/read.php?tid=34
這是回家才做的
這題我也爆掉 = =

小參 提到...

總算寫出來了。
相隔了將近一年才 AC 的 code 阿.....(遠目)

張貼留言