【問題G17】銷售員的最高獲利。            [回前頁]

假設過去之銷售員均是背著背袋沿街銷售, 現有一銷售員他有 n 樣貨品, 每樣 貨品之重量為 wi, 且每樣貨品銷售後可獲利 pi, 1<=i<=n ; 另假設他的貨袋承載量為 M, 請寫一程式為此銷售員決定該選裝那些貨才能有最高的獲利。(輸出所選載之貨, 總載重和, 及最高獲利值)

 說明:

 1. n, M, wi, pi 均為正整數

 2. 輸入資料格式 (共三列)

    n, M

    w1, w2, ... wn

    p1, p2, ... pn

 3. 輸出結果格式 (共三列)

    選裝之貨為 (w1, w2, ... wn)

    (註:選中者以其重量表示,未選中者則以0表示)

    總載重量 = x

    最高獲利 = Y

 4. 此程式執行完一組資料後要能從鍵盤繼續接受下一組輸入資料,直到輸入值 n=0時則結束

 5. 評分標準為程式之正確性及程式之反應時間, 故請勿用土法煉鋼方式來做

 範例:

      輸入資料:

        8, 110

        1, 11, 21, 23, 33, 43, 45, 55

        11, 21, 31, 33, 43, 53, 55, 65

      輸出結果:

        選裝之貨為 (1, 11, 21, 0, 33, 43, 0, 0)

        總載重量 = 109

        最高獲利 = 159