読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

aoj 0042

Aizu Online Judge c++ 動的計画法

泥棒 | Aizu Online Judge
0-1ナップサック問題.
abc 032 - Tamflexの貯蔵庫
でも書いたように大きく3種類の解法が考えられる.

  • 物体の集合を2分割し組み合わせをすべて試す
  • i番目までの物体を用いたとき重さjを実現できる最大の価値をdp[i][j]とおく
  • i番目までの物体を用いたとき価値jを実現できる最小の重さをdp[i][j]とおく

計算量はそれぞれ

  • O(n*2^(n/2))
  • O(N*WMAX)
  • O(N*VMAX)

今回は重さの合計の最大値が高々1000であるので2番目の方法が良いと考えられる.
ちなみに価値の最大値は1000*10000=10^7なので現実的ではない.

int W, N;
int v[1010];
int w[1010];

void solve()
{
  int dp[1010];
  fill_n(dp,1010,0);
  REP(i,N) DOWN(j,W,w[i])
    dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
  int ans1 = 0, ans2 = 0;
  DOWN(i,W,0) if(ans1 <= dp[i])
  {
    ans1 = dp[i];
    ans2 = i;
  }
  printf("%d\n%d\n",ans1,ans2);
}

int main()
{
  for(int c = 1; scanf("%d",&W), W; c++)
  {
    scanf("%d",&N);
    REP(i,N) scanf("%d,%d",&v[i],&w[i]);
    printf("Case %d:\n",c);
    solve();
  }
  return 0;
}