[ZJ][背包問題+Greedy] a455. TOI2010 第四題：商品特賣問題＠Morris' Blog

2012-09-16 09:27:30| 人氣2,768| 回應0 | 上一篇 | 下一篇

[ZJ][背包問題+Greedy] a455. TOI2010 第四題：商品特賣問題

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

內容：

　　在一個年終大拍賣活動中，一家迪化街的商店推出了一個特賣活動，老闆說只要你花錢買4個箱子，第一個箱子最多可裝30公斤的商品，第二個箱子最多可裝 40公斤的商品，第三個箱子最多可裝50公斤的商品，第四個箱子最多可裝25公斤的商品。可以挑選的商品有十種，重量分別是15, 16, 30, 18, 19, 20, 21, 25, 24, 及17公斤。每一種商品最多只能挑一次，且一種商品不可拆開分到不同箱子中。假設產品加總的重量小於等於箱子的限定重量就一定裝得下這些產品，由於每樣產品的售價一樣，因此若挑選能裝入4個箱子的商品種類愈多，便表示價值愈高。請你寫一個程式來算出最多可以裝入這些箱子的商品數目，以便估算是否划算。

輸入說明：

　　第一行為兩個整数M及N以空白區分，其中M表示箱子的個數，而N表示商品的種類數。

　　第二行開始的M行各為每一個箱子可容納的最大重量(公斤)。從第M+2行開始的N行，則分別表示N種商品個別的重量(公斤) 。

　　其中0<M≤50，0<N≤1000。

輸出說明：

　　顯示最多能够裝入這些箱子的商品數目。若找不到能裝入這些箱子的商品，請輸出0。

範例輸入： help

範例輸出：

範例一：
7

範例二：
7

提示：

時限仿照原題，更改為10秒。 (2012/7/6 修改)

出處：

2010 TOI 研習營初選 (管理：longbiau)

隨便做的做法, 不保證正確性

#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <algorithm>
#include <functional>
using namespace std;
char p[1000][3000];
int main() {
    int m, n, i, j, k;
    int C[1005], W[1005];
    while(scanf("%d %d", &m, &n) == 2) {
        for(i = 0; i < m; i++)
            scanf("%d", &C[i]);
        for(i = 0; i < n; i++)
            scanf("%d", &W[i]);
        sort(C, C+m);
        sort(W, W+n, greater<int>());
        int used[1000] = {};
        int ans = 0;
        for(i = 0; i < m; i++) {
            int dp[3000] = {};
            int mx = 0, tmpN;
            memset(p, 0, sizeof(p));
            dp[0] = 0;
            for(j = 0; j < n; j++) {
                if(used[j] == 0) {
                    for(k = C[i]; k >= 0; k--) {
                        if(k-W[j] >= 0 && dp[k-W[j]]+1 > dp[k]) {
                            dp[k] = dp[k-W[j]]+1;
                            p[j][k] = 1;
                        }
                    }
                }
            }
            mx = dp[C[i]];
            if(mx == 0) break;
            ans += mx;
            for(j = n-1, k = C[i]; j >= 0; j--) {
                if(p[j][k]) {
                    used[j] = 1;
                    k -= W[j];
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

我要檢舉

#a455#TOI2010#第四題#商品特賣問題

台長： Morris

您可能對以下文章有興趣

[ZJ][BIT] a484. 美麗風景遞增之路

[ZJ][模擬、旋轉] b125. 積木的拼疊問題（Bricks）

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

[NOIP][dp背包] 2006 2.金明的预算方案

人氣(2,768) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ZJ][sort] a480. 導彈攔截系統
此分類上一篇:[ZJ][多重背包+Greedy] a350. 3. 緞帶的購買問題

回應(0)