Online Judge►UVa

[UVa] 233 - Package Pricing

題意

有一間大賣場在做促銷，有4種燈泡要賣，於是推出了組合包，每一種組合包會有自己的序號、價錢、內容物，請依據需求算出最便宜的買法且輸出買法。

解法

可利用整數線性規畫或是無限背包問題，從學長得知四項需求相乘不會超過100萬，所以可以使用背包問題的做法，要注意邊界。

1
dp[i][j][k][l][m] = min(dp[i-1][j][k][l][m],dp[i][j-w[i]][k-w[i]][l-w[i]][m-w[i]]+c[i])

當然這樣子做空間會爆炸，所以必須空間優化。

1
dp[j][k][l][m] = min(dp[j][k][l][m],dp[i][j-w[i]][k-w[i]][l-w[i]][m-w[i]]+c[i])

原本打算一次建好表，但反而每次依據需求大小重新建表來的快。

心得

不斷送出得到WA，最後詢問學長後得知是處理浮點數上出了問題，所以直接字串處理成整數再運算。而其中並不會有0.00的價錢存在，原本折騰了許久……。

等之後再來研究線性規畫的做法。

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
102
103
#include <iostream>
#include <vector>
#include <sstream>
#include <iomanip>
#include <map>
using namespace std;
#define maxnumber 9999999
int main()
{
	int n , m , b = 0 ;
	while ( cin >> n && !cin.eof() ) {
		vector <int> number(n+1) ;
		vector <int> price(n+1) ;
		vector <vector<int> > table(n+1,vector<int>(4,0)) ;
		cin.ignore();
		string input ;
		stringstream ss ;
		string money ;
		char c ;
		for ( int n2 = 1 , digit , sum = 0 ; n2 < n + 1 && getline(cin,input) ; n2 ++ , sum = 0 ){
			ss << input << " x " ;
			ss >> number[n2] >> money ;
			for ( int i = 0  ; i < money.length() ; i ++ ){
				if ( money[i] == '.' )
					continue ;
				sum *= 10 ;
				sum += (int)money[i] - 48 ;
			}
			price[n2] = sum ;
			while ( ss >> c && c != 'x' ){
				ss >> digit ;
				table[n2][(int)c - 97] += digit ;
			}
		}
		map <int , int> amount ;
		cin >> m ;
		cin.ignore();
		for ( int m2 = 0 , digit ; m2 < m && getline(cin,input) ; m2 ++ ){
			int sum[4] = { 0 , 0 , 0 , 0 } ;
			ss << input << " x " ;
			while ( ss >> c && c != 'x' ){
				ss >> digit ;
				sum[(int)c - 97] += digit ;
			}
			vector<vector<vector<vector<int> > > >  dp(sum[0]+1,vector<vector<vector<int> > >
														 (sum[1]+1,vector<vector<int> >
														 (sum[2]+1,vector<int>
														 (sum[3]+1,maxnumber) ))) ;
			dp[0][0][0][0] = 0 ;
			for ( int i = 1 ; i < n + 1 ; i ++ ){
				for ( int j = 0 ; j < sum[0] + 1  ; j ++ ){
					for ( int k = 0 ; k < sum[1] + 1 ; k ++  ){
						for ( int l = 0 ; l < sum[2] + 1 ; l ++  ){
							for ( int q = 0 ; q < sum[3] + 1; q ++   ){
								int s1 , s2 , s3 , s4 ;
								s1 = j-table[i][0] , s2 = k-table[i][1] , s3 = l-table[i][2] , s4 = q-table[i][3] ;
								if ( s1 < 0 ) s1 = 0 ;
								if ( s2 < 0 ) s2 = 0 ;
								if ( s3 < 0 ) s3 = 0 ;
								if ( s4 < 0 ) s4 = 0 ;
								dp[j][k][l][q] = min(dp[j][k][l][q],dp[s1][s2][s3][s4]+price[i]) ;
							}
						}
					}
				}
			}
			cout << m2+1 << ":" << setw(8) << fixed << setprecision(2) << ((double)dp[sum[0]][sum[1]][sum[2]][sum[3]])/100 ;
			amount.clear();
			int s1 = sum[0] , s2 = sum[1] , s3 = sum[2] , s4 = sum[3] , n3 = 1 ;
			while (  n3 <= n  ){
				int temp1 = s1-table[n3][0] , temp2 = s2-table[n3][1] , temp3 = s3-table[n3][2] , temp4 = s4-table[n3][3] ;
				if ( temp1 < 0 ) temp1 = 0 ;
				if ( temp2 < 0 ) temp2 = 0 ;
				if ( temp3 < 0 ) temp3 = 0 ;
				if ( temp4 < 0 ) temp4 = 0 ;
				if ( dp[s1][s2][s3][s4] - dp[temp1][temp2][temp3][temp4] == price[n3] ){
					amount[number[n3]] ++ ;
					s1 = temp1 , s2 = temp2 , s3 = temp3 , s4 = temp4 ;
				} else {
					n3 ++ ;
				}
			}
			for ( map<int,int>::iterator iter = amount.begin() ; iter != amount.end() ; iter ++ ){
				if ( iter-> second == 1 )
					cout << " " << iter->first ;
				else
					cout << " " << iter->first << "(" << iter->second << ")" ;
			}
			ss.clear();
			dp.clear();
			cout << endl ;
		}
		table.clear();
		number.clear();
		price.clear();
		amount.clear();
		cout << endl ;
	}
	return 0;
}