USACO Section 5.3 Milk Measuring - DFSID＋DP...

网友投稿 296 2022-11-28

USACO Section 5.3 Milk Measuring - DFSID＋DP...

这道题要是不要写具体方案数就很普通的可重复背包了..对一个bool数组进行DP...从1做到Pnum..每次当k空间的k-P[i]为可得到时..k空间则可得到...每次扫描空间从0到Q.最后当Q为true..这些物品各种可重复的组合说能得到Q...

但要求具体的方案数就eggache了..开始我想用一个当在做重复背包的时候跟着判断并传递...每个空间不为bool...而是一个struct..包括到达这个空间的最小物品数..以及按字典序最小的那几个..也就是

struct node { int num,a[105]; }

应该是行得通的...空间来说Q最大20000...每个空间挂100的int数组..那么相当于开了个2000000的int 数组.在USACO允许的空间内..

既然这节的TEXT就是写的搜索...我还是练了下DFSID...2分枚举当且查找方案的所用物品个数...然后搜能否得到解...而当判断有无解时就是一样的可重复背包..能背出Q就是可行解...不难发现若先搜较小的数更容易提前搜出答案...所以对P先排序...

这里有个很强劲的剪枝...就是边往深层DFS一种方案时..当枚举的当且某物品单个大小前面就能背出来..那就没必要再以这个物品往下搜了..因为这个物品的单个价值前面能得到..那么它与所有的数怎么怎么样相加都不能对背包空间做出任何更新....

还有个比较重要的剪枝..当搜(1,2)..显然得到的结果与搜(2,1)一样..所以在DFS搜一种方案时就要保证每一层所选择的物品必须在上一层的后面...

Program:

/* ID: zzyzzy12 LANG: C++ TASK: milk4*/ #include #include #include #include #include #include#include#include #include #define oo 2000000005 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std;int Q,N,P[105],num,ans[105];int now[105],nownum;bool can[30001];bool DFS(int i,int k){ int j; bool temp[30001]; if (can[Q]) { if (num>nownum) { num=nownum; for (j=1;j<=num;j++) ans[j]=now[j]; } return true; } if (!k) return false; for (;i<=N;i++) if (!can[P[i]]) { for (j=0;j<=Q;j++) temp[j]=can[j]; for (j=0;j<=Q-P[i];j++) if (can[j]) can[j+P[i]]=true; now[++nownum]=P[i]; if (DFS(i+1,k-1)) return true; nownum--; for (j=0;j<=Q;j++) can[j]=temp[j]; } return false;}bool ok(int k){ if (k>N) return false; int i; memset(can,false,sizeof(can)); can[0]=true; nownum=0; if (DFS(1,k)) return true; return false;}void getanswer(){ int l,r,mid; num=oo; r=1; while (!ok(r)) r*=2; l=r/2; while (r-l>1) { mid=(r+l)/2; if (ok(mid)) l=mid; else r=mid; } return;}int main() { freopen("milk4.in","r",stdin); freopen("milk4.out","w",stdout); scanf("%d%d",&Q,&N); int i; for (i=1;i<=N;i++) scanf("%d",&P[i]); sort(P+1,P+1+N); getanswer(); printf("%d",num); for (i=1;i<=num;i++) printf(" %d",ans[i]); printf("\n"); return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：排序 方案
上一篇:HDOJ 4578/2013年杭州邀请赛C题 - Transformation 线段树...比较蛋疼的维护PushDown
下一篇:iReport使用指南及常见功能示例详解
相关文章

 发表评论

暂时没有评论，来抢沙发吧~