PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 樂透號碼最佳化的問題

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間13年前 (2011/02/22 21:39)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串5/9 (看更多)

看到這個題目，直覺就是coin change的DP解。提到換零錢應該很多人都可以想出解答了。的確，這取決於獎金總和開陣列是否記憶體能撐得住。附上程式碼和點題。總之，對於[目前金額 - 獎金]，如果[]是有解的，並且加總開獎號碼小於等於5個號碼時，目前金額的號碼就要累計加總的開獎號碼。另外，這個程式碼可能開出3個號碼(小於5個)但金額最高，那就請你任選2個多餘的號碼搭配成5個。另外2，如果開2個和開5個會是相同的獎金總和，會跑出開5個。程式碼不到100行，應該不難看懂。 #include <iostream> #include <vector> #include <set> using namespace std; const int BIT = 21; int count_bit(int n) { int ret = 0; n >>= 1; for(int i = 1; i < BIT; ++i, n >>= 1) { ret += n & 1; } return ret; } int main() { int cases; scanf("%d", &cases); while(cases--) { int n; // data size scanf("%d", &n); vector<int> coin(n); vector<int> coin_bit(n, 0); int q; // number size int num; // number int sum = 0; // sum of coin for(int i = 0; i < n; ++i) { scanf("%d%d", &coin[i], &q); sum += coin[i]; for(int j = 0; j < q; ++j) { scanf("%d", &num); coin_bit[i] |= 1 << num; } } vector< set<int> > method(sum + 1); method[0].insert(0); for(int i = 0; i < n; ++i) { for(int j = sum; j >= coin[i]; --j) { int k = j - coin[i]; if(method[k].size()) { set<int> :: iterator it = method[k].begin(); while(it != method[k].end()) { int new_int = *it | coin_bit[i]; if(count_bit(new_int) <= 5) { method[j].insert(new_int); } ++it; } } } } int total = 0, max_bit = 0, max_value = 0; for(int i = sum; i > 0; --i) { int size = method[i].size(); if(size > 0) { total = i; set<int> :: iterator it = method[i].begin(); while(it != method[i].end()) { int j = count_bit(*it); if(max_bit < j) { max_bit = j; max_value = *it; } ++it; } break; } } if(total > 0) { printf("%d, ", total); printf("choose: "); max_value >>= 1; for(int i = 1; i < BIT; ++i, max_value >>= 1) { if(max_value & 1) { printf("%d ", i); } } puts(""); } else { puts("none"); } } return 0; } 有錯跟我說，我再改。 Bleed ※ 引述《shipship (Ship)》之銘言： : 最近在跑一個模擬，遇到一個最佳化問題請各位板大幫忙看看: : 現有一個對獎系統，從20個號碼中選5個做為這次的中獎號碼 : 有一群下注資料，格式如下： : 978 3 2 10 13 //獎金978元，買了三個號碼，分別為2,10,13 : 5921 2 1 14 : 8027 4 1 4 6 9 : 7931 4 5 9 10 15 //獎金7931元，買了四個號碼，分別為5,9,10,15 : 4957 2 2 16 : 中獎的條件是該客人所買的號碼全中(全部都在5個中獎號碼中出現) : 假設今日開獎號碼為1 2 4 10 13 16 : 則總獎金為978+4957 : 請求出，開出哪5個號碼，可以使得大家所得到的獎金最高？ : 每個人可以買的號碼數量為2~5，資料筆數不超過六千 : 我想了好久，目前都出的演算法，分析一下都還是暴力解。 : 請板大有甚麼意見請踴躍討論感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.43.115.234