D - 荷物の配達 / Package Delivery 解説
by 
MMNMM
解法を思いつく道筋について
前から荷物を見ていって、そこまでの荷物の選び方を管理することを考えてみます。 前から \(k\) 個の荷物を見たとき、そこまでの荷物の選び方は \(2 ^ k\) 通りあります。 \(50\) 個の荷物を見たときの選び方 \(2 ^ {50}\) は非常に多いため、選び方を絞る必要があります。
まず、荷物の重量はすべて正なので、最終的な重量の合計は今の重量の合計を下回りません。 よって、現在の合計の重量が \(S\) を越える選び方を覚えておく必要はありません。 また、\(2\) つの選び方 \(A,B\) について、
- \(A\) で選んだ個数は \(B\) で選んだ個数以下
- \(A\) で選んだ荷物の重量の合計は \(B\) で選んだ荷物の重量の合計以下
- \(A\) で選んだ荷物の純利益の合計は \(B\) で選んだ荷物の純利益の合計以上
という関係が成り立っているとき、選び方 \(B\) を覚えておく必要はありません（最終的に、選び方 \(B\) にこのあと見る荷物をいくつか追加したものが条件を満たすなら、同じ荷物を選び方 \(A\) に追加したものも条件を満たすためです）。
よって、次のような条件を満たす選び方だけを覚えておけばよいです。
- 選んだ個数が \(n\) 個以下、重量の合計が \(w\) 以下であるような選び方のうち、純利益の合計が最大であるもの \((1\le n\le N,1\le w\le S)\)
これの先頭から荷物を \(k\) 個見た時点での値を \(\operatorname{dp} _ k[n][w]\) と書くことにしましょう。
新しく \(k+1\) 番目の荷物を見たとき、\(\operatorname{dp} _ {k+1}\) を求める必要があります。 これは、 \(k+1\) 番目の荷物を選ぶか選ばないかを比較することに相当します。 具体的には、
- \(\operatorname{dp} _ k[n+1][w+W _ {k+1}]\)
- \(\operatorname{dp} _ k[n][w]\) に \(k+1\) 番目の荷物を追加したもの
の \(2\) つの選び方を比較し、より純利益の大きいほうを新しい \(\operatorname{dp} _ {k+1}[n+1][w+W _ i]\) とすればよいです。
これを繰り返してすべての荷物を見たあとの、\(\operatorname{dp} _ N[i][S]\) の純利益の合計が \(T\) 以上になるような最小の \(i\) が求める最小の個数です。
ここまで、\(\operatorname{dp} _ k[n][w]\) は「選び方」を管理していましたが、更新や最後の判定のときには「選び方の純利益の合計」さえわかっていれば十分です。
以上より、
- \(\operatorname{dp} _ k[n][w]\coloneqq k\) 番目までの荷物を使った、選んだ個数が \(n\) 個以下、重量の合計が \(w\) 以下であるような選び方に対する純利益の合計の最大値 \((1\le n\le N,1\le w\le S)\)
のように定義すると、効率的に管理・更新ができ、この問題を解くことができます。
これは、一般的なナップサック問題の DP（動的計画法）に個数の情報を付け加えたものだと思うことができます。
\(N\) 個の荷物を前から見て、荷物を見るたびに \(O(NS)\) 個の値を（定数時間で）更新するため、時間計算量は \(O(N ^ 2S)\) となります。
実装例は以下のようになります。
#include <iostream>
#include <vector>
using namespace std;
int main(){
int N, S, T;
cin >> N >> S >> T;
vector dp(N + 1, vector<int>(S + 1)); // [0 .. N] × [0 .. S] の DP テーブル
for (int i = 0; i < N; ++i) {
int P, C, W;
cin >> P >> C >> W;
for (int n = N; n--; ) { // n が大きいほうから（小さいほうから処理すると同じ荷物を重複して選んでしまう）
for (int w = 0; w + W <= S; ++w) { // 更新する範囲がはみ出ないように
dp[n + 1][w + W] = max(dp[n + 1][w + W], dp[n][w] + P - C); // 新しい荷物を選ぶか選ばないかを比較して更新する
}
}
}
for (int n = 0; n <= N; ++n) { // n が小さいほうから見ていって
if (dp[n][S] >= T) { // 個数が n 個以下で重量が S 以下である選び方の中で最大の純利益が T 以上なら
cout << n << endl; // 答えは n
return 0;
}
}
cout << -1 << endl; // なければ -1
return 0;
}
N, S, T = map(int, input().split())
dp = [[0 for _ in range(S + 1)] for _ in range(N + 1)] # [0 .. N] × [0 .. S] の DP テーブル
for _ in range(N):
P, C, W = map(int, input().split())
for n in reversed(range(N)): # n が大きいほうから（小さいほうから処理すると同じ荷物を重複して選んでしまう）
for w in range(S - W + 1): # 更新する範囲がはみ出ないように
dp[n + 1][w + W] = max(dp[n + 1][w + W], dp[n][w] + P - C) # 新しい荷物を選ぶか選ばないかを比較して更新する
for n in range(N + 1): # n が小さいほうから見ていって
if dp[n][S] >= T: # 個数が n 個以下で重量が S 以下である選び方の中で最大の純利益が T 以上なら
print(n)
break
else:
print(-1)
投稿日時:
最終更新: