解題區/解題區 - UVa

UVa 233 - Package Pricing

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

總共有 a, b, c, d 四種類型的燈泡，現在給予一些組合包的價格和各自內有四種類型的燈泡數量，現在要求購買指定個數以上的方案，求最少花費。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
5
10 25.00 b 2
502 17.95 a 1
3 13.00 c 1
55 27.50 b 1 d 2 c 1
6 52.87 a 2 b 1 d 1 c 3
6
d 1
b 3
b 3 c 2
b 1 a 1 c 1 d 1 a 1
b 1 b 2 c 3 c 1 a 1 d 1
b 3 c 2 d 1 c 1 d 2 a 1

Sample Output

1
2
3
4
5
6
1:   27.50 55
2:   50.00 10(2)
3:   65.50 3 10 55
4:   52.87 6
5:   90.87 3 6 10
6:  100.45 55(3) 502

Solution

這一題不外乎就是整數線性規劃，很明顯地是一個 NPC 問題，所以就兩種策略強力剪枝、背包問題。

關於強力剪枝，大概是當年解決問題的方法，因為題目沒有特別說明數據範圍，用背包問題是相當不方便的，我也搜索不到當年 WF 的 code，所以測試一下數據範圍，發現將四種類型燈泡需求相乘結果不大於 100 萬。

藉由這個條件，將狀態訂為 dp[a_size][b_size][c_size][d_size] 的最小花費為何，但是可能忽大忽小，所以自己定義 row major 來完成。嘗試將每一種組合去迭代找最小值，中間過程要記得取 min bound，以免越界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <assert.h>
#include <map>
#include <queue>
using namespace std;
struct COMB {
    int label, supply[4];
    double price;
    void init() {
        memset(supply, 0, sizeof(supply));
    }
    void print() {
        printf("%d %lf %d %d %d %d\n", label, price, supply[0], supply[1], supply[2], supply[3]);
    }
    bool operator<(const COMB &p) const {
        return label < p.label;
    }
} products[64];
int n, q, need[16];
int mnCnt[64], path[64];
double mnCost;
double dp[1048576];
int dpChoose[1048576][2];
int row[4];
int getIndex(int A[]) {
    int v = 0;
    for (int j = 0; j < 4; j++)
        v += A[j] * row[j];
    return v;
}
void bfs() {
    row[0] = (need[3]+1)*(need[2]+1)*(need[1]+1);
    row[1] = (need[3]+1)*(need[2]+1);
    row[2] = need[3]+1;
    row[3] = 1;
    int A[4], B[4], u, v, mxState = getIndex(need);
    for (int i = 0; i <= mxState; i++)
        dp[i] = 1e+50, dpChoose[i][0] = dpChoose[i][1] = -1;
    dpChoose[0][1] = -1, dp[0] = 0;
    for (int p = 0; p <= mxState; p++) {
        u = p;
        for (int i = 0; i < 4; i++)
            A[i] = u / row[i], u %= row[i];
        u = p;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 4; j++)
                B[j] = min(A[j] + products[i].supply[j], need[j]);
            v = getIndex(B);
            if (dp[v] > dp[u] + products[i].price)
                dp[v] = dp[u] + products[i].price, dpChoose[v][0] = i, dpChoose[v][1] = u;
        }
    }
    memset(mnCnt, 0, sizeof(mnCnt));
    for (int p = mxState; p != -1; p = dpChoose[p][1])
        mnCnt[dpChoose[p][0]]++;		
    mnCost = dp[mxState];
}
int main() {
    char line[1024];
    string token;
    int cnt = 0;
    while (scanf("%d", &n) == 1) {
        while (getchar() != '\n');
        
        for (int i = 0; i < n; i++) {
            products[i].init();
            gets(line);
            stringstream sin(line);
            sin >> products[i].label >> products[i].price;
            while (sin >> token >> cnt)
                products[i].supply[token[0] - 'a'] += cnt;
        }
        sort(products, products + n);
        gets(line);
        sscanf(line, "%d", &q);
        for (int i = 0; i < q; i++) {
            memset(need, 0, sizeof(need));
            gets(line);
            stringstream sin(line);
            while (sin >> token >> cnt)
                need[token[0] - 'a'] += cnt;
            bfs();
            printf("%d:%8.2lf", i + 1, mnCost);
            for (int j = 0; j < n; j++) {
                if (mnCnt[j]) {
                    printf(" %d", products[j].label);
                    if (mnCnt[j] > 1)
                        printf("(%d)", mnCnt[j]);
                }
            }
            puts("");
        }
        puts("");
    }
    return 0;
}