仲恺建设局网站,wordpress CodeMirror,网站跳转微信链接,阿里云服务器ip做网站题意#xff1a;给定最大贴邮票上限和若干个邮票组合#xff0c;求最大的连续邮资的一个组合#xff0c;如果有多个#xff0c;按字典序输出最大的一个。 思路#xff1a;对每一组邮票#xff0c;求出当邮资为i时需要邮票数的最小值d[i]#xff0c;边界为d[0]0、d[i]给定最大贴邮票上限和若干个邮票组合求最大的连续邮资的一个组合如果有多个按字典序输出最大的一个。 思路对每一组邮票求出当邮资为i时需要邮票数的最小值d[i]边界为d[0]0、d[i]s时break。属于01背包问题。 code #include bits/stdc.h
using namespace std;#define cls(a,c) memset(a,c,sizeof (a))
#define ft(i,s,t) for (int is;it;i)
const int N15,M1005;
int m,k,n;
int mb[N];
int a[N][N],b[N][N];
int f[M];void sol(int k,int n){cls(f,63);f[0]0;ft(i,1,m) ft(j,1,n){if (ia[k][j]) continue;f[i]min(f[i],f[i-a[k][j]]1);}
}
int main()
{while (~scanf(%d %d,k,n),k){int ans0,id;ft(i,1,n){scanf(%d,mb[i]);ft(j,1,mb[i]) scanf(%d,a[i]j),b[i][j]a[i][j];sort (a[i]1,a[i]mb[i]1);mk*a[i][mb[i]];sol(i,mb[i]);ft(j,1,m){if (f[j]kjm) continue;if (f[j]k) j--;if (ansj) ansj,idi;else if (ansj){int tmb[i];if (tmb[id]) idi;else if (tmb[id]a[i][t]a[id][t]) idi;}break;}}printf(max coverage %4d :,ans);ft(i,1,mb[id]) printf(%3d,b[id][i]);puts();}
}
