JOI 本選 2014 B - IOI饅頭 (AOJ 0599, 難易度 6)

まさにナップサック問題！！！

• 問題へのリンク

問題概要

個の饅頭がある。それぞれ 円で売り出そうとしている (全部売るとは限らない)。

饅頭を得るための箱をいくつか購入することにした。箱は 種類あって、 番目の箱は

• 饅頭を 個まで詰められる
• 仕入れるのに 円を要する

いくつかの箱を購入して、それらの箱に饅頭を詰めて売り出したい。売ろうとした饅頭はすべて売れると仮定したときに、得られる利益の最大値を求めよ。

制約

• 
• 
• 

考えたこと

もし箱を 1 個も購入せず、饅頭も 1 個も売らないとすると、利益は 0 円になる。よって答えが負になることはない。

あらかじめ、以下の情報を前処理で求めておくと便利だと思った。

• profit[ n ] := 合計で n 個の饅頭を売った場合の、饅頭の売り上げの最大値 (箱を仕入れる費用はここでは加味しない)

これは、饅頭の値段 を大きい順にソートして、累積和をとることで求められる。

n 個の饅頭を箱詰めできるための箱費用の最小値

残る問題は、n 個の饅頭を売りたいと考えた場合の、箱購入に要するコストの最小値を求める部分。

これはナップサック問題 (の反対) になっている。ナップサック問題は容量 以下になるように選んだ品物の価値の総和の最大値を求める問題だが、今回は

「詰められる饅頭の個数の合計値が 以上となるように選んだ箱の費用の総和の最小値を求める問題」

となっている。少し違うだけで、これもナップサック問題に対する DP と同様の DP で解ける。計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

// 利益: profit[n] = n コの饅頭を乗っけられるとしたときの最大利益
// mincost[n] = n コの饅頭を売れるような箱のコストの総和の最小値 
// mincost を計算する部分は、まさにナップサック問題
int main() {
    long long M, N;
    cin >> M >> N;
    vector<long long> A(M), profit(M+1, 0);
    for (int i = 0; i < M; ++i) cin >> A[i];
    sort(A.begin(), A.end(), greater<long long>());
    for (int i = 0; i < M; ++i) profit[i+1] = profit[i] + A[i];

    const long long INF = 1LL<<60;
    vector<long long> C(N), E(N);
    for (int i = 0; i < N; ++i) cin >> C[i] >> E[i];
    vector<long long> dp(M+1, INF);
    dp[0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = M; j >= 0; --j) {
            chmin(dp[min(j+C[i], M)], dp[j] + E[i]); 
        }
    }

    long long res = 0;
    for (int n = 0; n <= M; ++n) {
        res = max(res, profit[n] - dp[n]);
    }
    cout << res << endl; 
}