作者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