Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2460-1d30b8e6
この記事にトラックバックする(FC2ブログユーザー)

SRM598 DIV1 EASY - BinPacking (この記事を編集する[管理者用])

Source

TopCoder SRM598 DIV1 EASY (250pt)
Problem Statement

問題概要

$N$ 個のアイテムがあり,$k$ 番目のアイテムの重さは $W_k$ である.
$1$ 個のビンには合計で重さ $300$ までのアイテムを入れることができる.
全てのアイテムを入れるためのビンの数の最小値を求める問題.
$1 \leq N \leq 50$
$100 \leq W_k \leq 300$

解法

まず,重さ $100$ のアイテム以外は高々 $2$ 個までしか同じ瓶に入れることができない.
よって,重さ $100$ のアイテムをどれだけ同じビンに $3$ つ詰め込むかを全探索して,残りはgreedyに詰め込めば良い.(以下の解答)
また,重さ $200$ のアイテムは重さ $100$ のアイテムと一緒に詰め込むほうが良いので,各ビンに対して重いアイテムから詰め込めるだけつめ込むというgreedyでも良い.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int solve(vector<int> in, int mx){
  int i, j, k, n;
  int res = 0;

  while(in.size()){
    n = in.size();
    sort(in.begin(), in.end());

    if(n >= 3 && in[2]==100 && mx > 0){
      res++;
      mx--;
      rep(i,3) in.erase(in.begin());
      continue;
    }

    for(i=n-2;i>=0;i--){
      if(in[i]+in[n-1] <= 300){
        res++;
        in.erase(in.begin() + (n-1));
        in.erase(in.begin() + i);
        break;
      }
    }
    if(i>=0) continue;

    in.pop_back();
    res++;
  }

  return res;
}

class BinPacking {
public:
int minBins(vector <int> in) {
  int i, j;
  int res = 10000;

  rep(i, 60){
    j = solve(in, i);
    res = min(res,j);
  }

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2460-1d30b8e6
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。