作者bleed1979 (十三)
站內Prob_Solve
標題Re: [問題] 樂透號碼最佳化的問題
時間Tue Feb 22 21:39:16 2011
看到這個題目，直覺就是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