AOJ : 1237 - Shredding Company
問題概要
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1237
問題文中の図のように, ターゲットナンバーが書かれた箱と, 数字が書かれた紙があります.
箱は, 紙を数字の切れ目のところで, いくつかに切り分けることができます.
紙を切り分けたとき, 各紙の数字の合計がターゲットナンバー以下であるものの内, 合計が最大になるような切り分けかたを出力する問題です.
例えば, ターゲットナンバーが 50 で, 紙が 12346 と書かれていて, 1, 2, 34, 6 と切り分けると, その合計値は, 43 となり, 50 以下の中で最大の数字でこれが答えとなります.
また, 最大となる切り分け方が複数ある場合は "rejected", そもそもそのような切り分け方がない場合は "error" と出力します.
アルゴリズム
深さ優先探索で解けます.
紙を何分割するかだけ決めて, あとは全切断パターンを試しました.
(途中で合計値がターゲットナンバーより大きくなる場合は, 枝刈りとか一応してます)
紙に書いてある数字が高々6ケタという条件が書いてあるため, これで十分間に合います.
プログラミング
string s; //yの文字列表記 int x,y,len; int ans[6],ansSize,ansSum,ansFlg; int tmp[6],size; void solve(int rem,int idx,int sum){ if(rem == 0 && idx == len){ if(ansSum < sum && sum <= x){ //最大ならば更新 for(int i=0;i<size;i++) ans[i] = tmp[i]; ansSize = size; ansSum = sum; ansFlg = 2; } else if(ansSum == sum) ansFlg = 1; //最大が複数出ると"rejected" return; } if(rem <= 0 || idx >= len) return; for(int nidx=idx+1;nidx<=len;nidx++){ string sub = s.substr(idx,nidx-idx); int plus = atoi(&sub[0]); if(sum + plus <= x){ //ターゲットナンバーを超える場合は枝刈する tmp[size-rem] = plus; solve(rem-1,nidx,sum+plus); } } } string itos(int x){stringstream ss; ss<<x; return ss.str();} int main(void){ while(cin>>x>>y,x||y){ s = itos(y); len = s.length(); ansFlg = size = 0; ansSum = -1; //分割数の決定 for(size=1;size<=len;size++){ solve(size,0,0); } if(ansFlg == 0) cout<<"error\n"; else if(ansFlg == 1) cout<<"rejected\n"; else{ cout<<ansSum; for(int i=0;i<ansSize;i++) cout<<" "<<ans[i]; cout<<endl; } } return 0; }