AtCoder Regular Contest #073/AtCoder Beginner Contest #060 D問題 - Simple Knapsack

Source

AtCoder Regular Contest #073
AtCoder Beginner Contest #060
問題文 (ARC)
問題文 (ABC)

問題概要

$N$ 種のアイテムが $1$ 個ずつあって,$i$ 番目のアイテムの価値は $V_i$,重さは $H_i$ である.
バッグには合計で重さ $W$ まで入れることができる.
バッグに入れるアイテムの価値の合計値を最大化した時,その最大値を求める問題.

解法

重さの種類数が $4$ 種類しかないので,アイテムを重さに応じて $4$ 種類に分類する.
後は,同じ重さなら価値が高い方からバッグに詰めれば良いので,各価値のアイテムを何個積めるかを全探索する.
$3$ 種類について,何個入れるかを決めると,最後の種類について何個入れるかは(できるだけ入れたほうが良いので)一意に定まる.
よって,時間計算量は $O(N^3)$ 程度でできる.

cLayversion 20170429-1)のコード

C++に変換後のコードはこちら

int N, W, H[100], V[100];
int gain[4][100], sum[4][101], sz[4];
{
  int res = 0;
  int a, b, c, d;
  ll r, minH;
  rd(N, W, (H,V)(N));
  minH = H[0];
  H[0..N-1] -= minH;
  gain[H[0..N-1]][sz[H[0..]]++] = V[0..];
  sort(gain[0..3], gain[0..]+sz[0..], greater<int>());

  sum[0...3][1..sz[0...]] += sum[0...][0..] + gain[0...][0..];

  rep(a,sz[0]+1) rep(b,sz[1]+1) rep(c,sz[2]+1){
    r = W - minH*a - (minH+1)*b - (minH+2)*c;
    if(r < 0) break;
    d = min(r / (minH+3), (ll)sz[3]);
    res >?= sum[0][a] + sum[1][b] + sum[2][c] + sum[3][d];
  }
  wt(res);
}

Current time: 2017年09月25日11時44分57秒
Last modified: 2017年04月29日23時01分12秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest AtCoder_Beginner_Contest ARC073 ARC_B ABC060 ABC_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン: