# Poj Solution 1882

```http://poj.org/problem?id=1882

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define NMAX 101
#define INF 10000
int anset[NMAX],alen,min;
int m[10020];
int t[NMAX];
int N,S,len;
void solve()
{
int i,j;
m[0]=0;
i=1;
while(1)
{
m[i]=INF;

for(j=0;j<len;j++)
{
if(t[j]>i)
break;
if(m[i]>m[i-t[j]]+1)
{
m[i]=m[i-t[j]]+1;
}

}
if(m[i]>S)
break;
i++;
}
i--;
if(min<i)
{
min=i;
alen=len;
memcpy(anset,t,sizeof(t));
}
else if(min==i)
{
if(alen>len)
{
alen=len;
memcpy(anset,t,sizeof(t));
}
else if(alen==len)
{
if(anset[alen-1]>t[len-1])
memcpy(anset,t,sizeof(t));
}
}
}
void output()
{
int i;
printf("max coverage = %d :",min);
for(i=0;i<alen;i++)
printf(" %d",anset[i]);
printf("n");
}
int main()
{
#if debug
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int i;
scanf("%d",&S);
while(S)
{
scanf("%d",&N);
min=-1;
while(N--)
{
scanf("%d",&len);
for(i=0;i<len;i++)
{
scanf("%d",&t[i]);
}
solve();

}
output();
scanf("%d",&S);
}
#if debug
fclose(stdin);
fclose(stdout);
#endif;
return 1;
}
```
This entry was posted in poj. Bookmark the permalink.