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;
}