yukicoder No.50 - おもちゃ箱

Source

ニコニコミュニティ
問題文

問題概要

$N$ 個のアイテムと $M$ 個の箱がある．
アイテム $k$ の容積は $A_k$ で，箱 $k$ は合計で容積 $B_k$ 以下になるアイテムを収納することができる．
全てのアイテムを収納するのに使う箱の数の最小値を求める問題．
あるいは，不可能であればそれを指摘する．

解法

箱は大きい箱から使えば良いので，大きい箱から順番に並び替えておく．
動的計画法を行う．
状態として，まだ入れていないアイテムの集合とし，今まで使い切った箱の数と，今使っている箱に既に収納した容積の最小値を計算する．
この時，使いきった箱の数が小さければ，そっちの方を小さいとし，使いきった箱の数が同じであれば，今使っている箱の容積が小さい方を小さいとする．
時間計算量は $O(N 2^N + M \log M)$ 程度．
各箱に収納するアイテムの集合をまとめて処理したりして，$O(N 2^N + 3^N)$ などのDPでも良い（以下のコードはこのタイプのDPだが手抜きして $O(N^4)$）．
アイテムを入れる順番を全部試し，今使っている箱に入るなら入れて，そうでなければ次の箱に入れるなどといった全探索でも一応通る．
この全探索は，時間計算量 $O(N \times N! + M \log M)$ 程度．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

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

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}

#define INF 10000000

int N, A[100], M, B[100];

int dp[1111], ok[1111], oks;

int main(){
  int i, j, k, mm;
  int res;
  int X;

  reader(&N);
  rep(i,N) reader(A+i);
  reader(&M);
  rep(i,M) reader(B+i);

  sort(B, B+M);
  reverse(B, B+M);

  rep(i,1<<N) dp[i] = INF;
  dp[0] = 0;
  
  rep(mm,M){
    X = B[mm];
    oks = 0;
    rep(i,1<<N){
      k = 0;
      rep(j,N) if(i&1<<j) k += A[j];
      if(k <= X) ok[oks++] = i;
    }
    
    for(i=(1<<N)-1;i>=0;i--) if(dp[i]<INF) rep(j,oks){
      dp[i|ok[j]] = min(dp[i|ok[j]], dp[i]+1);
    }
    if(dp[(1<<N)-1] < INF) break;
  }
  res = dp[(1<<N)-1];
  if(res==INF) res =-1;
  writer(res,'\n');

  return 0;
}

Current time: 2024年04月20日03時14分52秒
Last modified: 2014年12月05日01時31分40秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：