题意：
容量为s的信封，给n组邮票的面值，求哪一组能组成的连续的面值的最大值最大，若有多组答案，输出面值数量最小的一组，若数量相等，输出最大面值最小的一组，若最大面值相等，输出第二大面值最小的一组，依次类推。
分析：
可以从小到大枚举面值直到不能组成，dp[i][j]是否能组成面值为i，用邮票数量为j dp[i][j]|=dp[i-v[k]][j-1],记忆化搜索即可
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <complex> #include <cassert> #include <utility> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; typedef pair<int,int> PII; typedef long long ll; #define lson l,m,rt<<1 #define pi acos(-1.0) #define rson m+1,r,rt<<11 #define All 1,N,1 #define read freopen("in.txt", "r", stdin) const ll INFll = 0x3f3f3f3f3f3f3f3fLL; const int INF= 0x7ffffff; const int mod = 1000000007; struct node{ int v1[15],len,d; }e[15]; bool cmp(node x,node y){ if(x.d!=y.d)return x.d>y.d; else if(x.len!=y.len)return x.len<y.len; else{ for(int k=x.len-1;k>=0;--k) if(x.v1[k]!=y.v1[k]) return x.v1[k]<y.v1[k]; } } int val[15][15],dp[1010][15],s,n; int dfs(int v,int num,int id) { if(dp[v][num]!=-1)return dp[v][num]; if(v==0) return dp[v][num]=1; if(num==0)return dp[v][num]=0; for(int i=1;i<=val[id][0];++i){ if(v>=val[id][i]&&dfs(v-val[id][i],num-1,id)) return dp[v][num]=1; } return dp[v][num]=0; } int main() { while(~scanf("%d",&s)&&s){ scanf("%d",&n); for(int i=0;i<n;++i){ scanf("%d",&val[i][0]); for(int j=1;j<=val[i][0];++j) scanf("%d",&val[i][j]); memset(dp,-1,sizeof(dp)); int v; for(v=1;;++v){ if(!dfs(v,s,i)){ v--; break; } } e[i].d=v; for(int k=1;k<=val[i][0];++k) e[i].v1[k-1]=val[i][k]; e[i].len=val[i][0]; } sort(e,e+n,cmp); printf("max coverage =%4d :",e[0].d); for(int i=0;i<e[0].len;++i){ printf("%3d",e[0].v1[i]); } printf("\n"); } return 0; }
;
原文：http://www.cnblogs.com/zsf123/p/4888469.html