【解題】錄製專輯 - 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");
}