SRM308 div2 difficult [典型的なナップサック問題]

#define TR_MAX 50
class TreasuresPacking {
private:
  typedef struct _things {
    int weight;
    int cost;
    bool flex;
  } Things;
public:
  double maximizeCost(vector  treasures, int W) {
    int sz = treasures.size();
    vector tr(sz);
    for(int i = 0; i < sz; i++) {
      char ch;
      sscanf(treasures[i].c_str(), "%d %d %c", &tr[i].weight,
	     &tr[i].cost, &ch);
      tr[i].flex = (ch == 'Y') ? true : false;
    }

    double dp[TR_MAX+1][W+1];  //dp[cnt+1][weight+1]
    memset(dp, 0, sizeof dp);
    for(int i = 0; i < sz; i++) {
      for(int j = 0; j < W; j++) {
	int tmpW = tr[i].weight;
//わりとここらへんがテクニック的だと思う．
//k = 0つまり、加えないときもループしているので、かならず一回は青色を通る．
	for(int k = 0; k <= tmpW; k++) {
	  if(tr[i].flex == false) {
	    if(k >= 1) k = tmpW;
	  }
	  if(j+k <= W) {
	    dp[i+1][j + k] = max(dp[i][j] + tr[i].cost * k*1.0 /tmpW, dp[i+1][j+k]);
	  } else {
	    break; //dp[i+1][j] = max(dp[i][j], dp[i+1][j])とかいらない．
	}

      }
    } //end for
    return *max_element(dp[sz], dp[sz]+W+1);
  }
//でも多分最悪の状態になったとき、時間が足りなくなりそう．
(i:50)*(j:10000)*(k:10000) 50億になっちゃう．

ここで、Wは1~10000とかなり範囲が広いので、配列のほとんどが使われない可能性がある．
そこで,mapをつかってdpをくむ。
そして、三重ループを２重ループになんとかしたいわけだが、普通ものをえらぶとき、コスパの高い方から順に選ぶ（どん欲法)ので、並び替えてdpを使うと良さそうということがわかる。

class TreasuresPacking {
private:
  typedef struct _things {
    int weight;
    int cost;
    bool flex;
  } Things;
<span class="deco" style="color:#FF0000;">//クラスは入れ子にできるよ．</span>
  class cmp {
  public:
//コスパの高い順に並べる．
    bool operator() (const Things& left, const Things& right) {
      return ((left.cost)*1.0/left.weight) > ((right.cost)*1.0/right.weight);
    }
  };
public:
  double maximizeCost(vector <string> treasures, int W) {
    int sz = treasures.size();
    vector<Things> tr(sz);
//INPUT
    for(int i = 0; i < sz; i++) {
      char ch;
      sscanf(treasures[i].c_str(), "%d %d %c", &tr[i].weight,
	     &tr[i].cost, &ch);
      tr[i].flex = (ch == 'Y') ? true : false;
    }
    sort(tr.begin(), tr.end(), cmp() );

    map<int, double> dp[sz+1];
    map<int, double>::iterator it;
    //trigger
    dp[0][0] = 0;

    //Dynamic Programming
    for(int i = 0; i < sz; i++) {
      for(it = dp[i].begin(); it != dp[i].end(); it++) {
	int j = it->first;
	int rem = W - j;

	if(rem >= tr[i].weight) {
	  rem = tr[i].weight;
	} else if(rem >= 0 && rem < tr[i].weight) {
	  rem = (tr[i].flex) ? rem : 0;
	}
//dp[i+1][j+rem]は存在しない可能性があるので、if(dp[i+1].equal_range(j+rem) == dp[i+1].end() )
//に応じて条件分岐しても良いが．そこまでこったことはしなくてよいだろうと判断．
	dp[i+1][j+rem] = max(dp[i][j] + (tr[i].cost)*rem*1.0/tr[i].weight, 
			     dp[i+1][j+rem]);
      }
    }
    double ans = 0;
    for(it = dp[sz].begin(); it != dp[sz].end(); it++) {
      ans = max(it->second, ans);
    }
    return ans;	
  }
//これで時間制限にひっかかることはないだろう．
おそらく求められているのは、mapを使うことではなくて、二重ループにすることだろう．