[ZJ][多重背包+Greedy] a350. 3. 緞帶的購買問題＠Morris' Blog

2012-09-16 07:38:02| 人氣1,253| 回應0 | 上一篇 | 下一篇

[ZJ][多重背包+Greedy] a350. 3. 緞帶的購買問題

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

小明的老師想要買緞帶來布置教室。她想要利用緞帶(緞帶的花色一樣)做成各種不同大小的花飾垂吊在教室後面，它們所需的緞帶長度分列如下：

花飾型號	A	B	C	D	E	F	G	H	I
緞帶長度	8	16	24	32	40	48	56	64	80

這些緞帶可以裁剪成適當的長度來製作花飾，所以一條緞帶可以製作二個以上的花飾。但緞帶無法拼接，所以若所剩之緞帶長度不足以製作花飾時只好捨棄。市面上所賣的緞帶長度是固定的，依進貨的批次不同而異。假設老師只能買到同一批次的緞帶，由於緞帶的價格昂貴，老師想要利用最少的緞帶來製作所需的花飾。給定市面上所賣的緞帶長度N以及各種花飾的數量，請你寫一個程式協助老師計算出所需購買的最少緞帶數。

輸入說明：

第一行有一個正整數N (10 £ N £ 500)，N代表目前市面上所賣的緞帶長度。

第二行有9個正整數C_i (1 £ i £ 9，0 £ C_i £ 1000)，以空白分開，依序代表各花飾型號所需的數量。第一個整數C₁為花飾型號A所需的數量，第二個整數C₂為花飾型號B所需的數量，以此類推。若不需製作某一型號的花飾，則C_i = 0。

輸出說明：

請輸出1個正整數，代表所需購買的緞帶數。若市面上所賣的緞帶長度過短以致於無法製作出所需的花飾，請輸出”NO SOLUTION!!”。

範例輸入：

輸入範例一
100
10 3 0 0 0 0 0 0 2


輸入範例二
70
0 0 0 0 0 0 0 0 100

範例輸出：

輸出範例一
3


輸出範例二
NO SOLUTION!!

提示：

出處：

100三重考區資訊學科能力競賽 (管理：pcshic)

這題是不是爛解過的我不知道, 但是我用以下的做法過了,
首先你要先了解什麼是多重背包
多重背包就是每件物品Ai有限制個數Ci, 在一個背包容量V的情況下, 價值最多為多少,
我當初以為多重背包是多個背包去拼湊, 所以沒有想那麼多, 但後來發現不是,
那 Greedy 的法則是什麼 ?
你必須由大容量的物品開始放置, 找到可以湊出最大容量的一組解, 之後從物品中剔除,
其中那一組解盡可能是字典順序最大的

#include <stdio.h>

int main() {
    int n, i, j, k;
    int A[10] = {0,1,2,3,4,5,6,7,8,10};
    while(scanf("%d", &n) == 1) {
        int C[10];
        for(i = 1; i <= 9; i++)
            scanf("%d", &C[i]);
        n /= 8;
        int ans = 0, sol = 1;
        while(1) {
            for(i = 1; i <= 9; i++)
                if(C[i])    break;
            if(i == 10) break;
            int dp[100] = {}, sour[100][2];
            dp[0] = 1;
            for(i = 9; i >= 1; i--) {
                if(C[i] > 0) {
                    for(j = n; j >= 0; j--) {
                        if(dp[j] == 0) {
                            for(k = 1; k <= C[i]; k++) {
                                if(j-k*A[i] < 0)    continue;
                                if(dp[j-k*A[i]]) {
                                    dp[j] = 1;
                                    sour[j][0] = i;
                                    sour[j][1] = k;
                                    break;
                                }
                            }
                        }
                    }
                }
            }
            int tmpN = n;
            while(tmpN >= 0 && dp[tmpN] == 0)   tmpN--;
            if(tmpN == 0)   {sol = 0;break;}

            while(tmpN) {
                C[sour[tmpN][0]] -= sour[tmpN][1];
                tmpN -= A[sour[tmpN][0]]*sour[tmpN][1];
            }
            ans++;
        }
        if(sol)
            printf("%d\n", ans);
        else
            puts("NO SOLUTION!!");
    }
    return 0;
}

我要檢舉

#a350#3. 緞帶的購買問題

台長： Morris

您可能對以下文章有興趣

[ZJ][N*NlogN][BIT] a533. IOI2004 Day1.1.阿特米斯

[ZJ][BFS] d373. 5. 乳酪的誘惑

[ZJ][dp] b220. 5. 蛋糕師傅的煩惱

[ZJ][二分+凸包計算面積] b221. 6. 耕者有其田

人氣(1,253) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ZJ][背包問題+Greedy] a455. TOI2010 第四題：商品特賣問題
此分類上一篇:[ZJ][spfa、尤拉路徑、bitmask] a416. 6. 城市馬拉松

回應(0)