首页 > 代码库 > poj 1416 Shredding Company (dfs)
poj 1416 Shredding Company (dfs)
链接:poj 1416
题意:有一种新的碎纸机,要用新的碎纸机将纸条上的数字切成几部分,
求切完后的和最接近而不超过target的值。
比如,target的值是50,而纸条上的数字是12346,应该把数字切成四部分,
分别是1、2、34、6。所得到的和43 (= 1 + 2 + 34 + 6) 是不超过50的最大和
比如1, 23, 4, 和6 ,和为34,比43小,
而12, 34, 6不可以,因为它们的和超过50了。
碎纸还有以下三个要求:
1、如果target的值等于纸条上的值,则不能切。
2、如果没有办法把纸条上的数字切成不超过target,则输出error。
如target是1而纸条上的数字是123,则无论你如何切得到的和都比1大。
3、如果有一种以上的切法得到最佳值,则输出rejected。
如target为15,纸条上的数字是111,则有以下两种切法11、1或者1、11.
如果有且仅有一种最佳方案,则输出最大值和切割的方案
思路:用dfs搜索每一种可能的情况,取不超过target的最大值,并记录分割的方案
#include<stdio.h> #include<string.h> int ans,m,n,vis[1000000],step[10],now[10],num; char s[10]; void dfs(int pos,int sum,int cnt) { int i,t; if(pos>=m){ vis[sum]++; if(sum>ans){ ans=sum; //记录最佳切割的和 num=cnt; for(i=0;i<cnt;i++) //记录当前最佳方案 step[i]=now[i]; } return ; } t=0; for(i=pos;i<m;i++){ t=t*10+s[i]-'0'; if(sum+t>n) return ; now[cnt]=t; dfs(i+1,sum+t,cnt+1); } } int main() { int i,sum; while(scanf("%d%s",&n,s)!=EOF){ m=strlen(s); if(n==0&&s[0]=='0'&&m==1) break; sum=0; for(i=0;i<m;i++) sum+=s[i]-'0'; if(sum>n){ //若最小的和都大于targe,则肯定不可能切割出不超过targe的和 printf("error\n"); continue; } memset(vis,0,sizeof(vis)); num=ans=0; dfs(0,0,0); if(vis[ans]>1) printf("rejected\n"); else{ printf("%d",ans); for(i=0;i<num;i++) printf(" %d",step[i]); printf("\n"); } } return 0; }
poj 1416 Shredding Company (dfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。