範例程式碼 uva242
//uva242
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 1010;
struct node{
vector<int> a;
bool operator < (const node& rhs) const {
if (a.size() < rhs.a.size()) return true;
else if (a.size() == rhs.a.size()) {
for (int i = 0; i < a.size(); i++) {
if (a[i] < rhs.a[i])
return 1;
if (a[i] > rhs.a[i])
return 0;
}
return false;
}
return false;
}
}plan[100];
bool d[maxn][11], vis[maxn][11];
int s, n, MAX[maxn];
int dp(int i, int j, int k) {
if (vis[i][j])
return d[i][j];
vis[i][j] = true;
if (i == 0)
return d[i][j] = 1;
d[i][j] = false;
for (int g = 0; g < plan[k].a.size(); g++) {
int fee = plan[k].a[g];
if (i >= fee && j > 0 && dp(i - fee, j - 1, k))
d[i][j] = true;
}
return d[i][j];
}
int CMP(const int a, const int b){
return a > b;
}
int main(void) {
while (scanf("%d", &s) && s) {
scanf("%d", &n);
for (int i = 0; i < n; i++)
plan[i].a.clear();
for (int i = 0; i < n; i++) {
int m;
scanf("%d", &m);
for (int j = 0; j < m; j++) {
int x;
scanf("%d", &x);
plan[i].a.push_back(x);
}
sort(plan[i].a.begin(), plan[i].a.end(), CMP);
}
sort(plan, plan + n);
int max_ = 0, posi = 0;
for (int i = 0; i < n; i++) {
MAX[i] = 0;
memset(vis, false, sizeof(vis));
for (int j = 1;; j++) {
if (!dp(j, s, i)) {
MAX[i] = j - 1;
break;
}
}
if (max_ < MAX[i])
max_ = MAX[i]; posi = i;
}
printf("max coverage =%4d :", max_);
for (int i = plan[posi].a.size() - 1; i >= 0; i--)
printf("%3d", plan[posi].a[i]);
printf("\n");
}
return 0;
}