基本的な動的計画法(価値が高い場合の01-ナップサック)

はじめに

問題は前回と同じで制約が異なります。

問題内容

重さ$${W}$$まで入るナップサックがあります。
荷物は$${N}$$個あり、$${i}$$番目の荷物は重さ$${w_i}$$で価値が$${v_i}$$です。
ナップサックに入れる荷物の価値の和の最大を求めてください。
ただし、同じ荷物を$${2}$$個以上入れることは許されません。

制約

$${1\le N\le 500}$$
$${1\le W\le 10^{12}}$$
$${1\le w_i\le 10^{12}}$$
$${1\le v_i\le 300}$$

解き方1. DFSで全探索

それぞれの荷物について入れるかどうか探索していきます。
計算量は$${O(2^N)}$$で不可能of不可能。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long int N,W,res=0;
long long int w[501],v[501];
void dfs(long long int id,long long int w_sum,long long int v_sum){
    if(w_sum>W){
        return;//重さがオーバーしたら終わり
    }
    if(id==N+1){
        res=max(res,v_sum);//価値の和の更新
        return;
    }
    dfs(id+1,w_sum,v_sum);//荷物を入れない
    dfs(id+1,w_sum+w[id],v_sum+v[id]);//荷物を入れる
    return;
}
int main() {
    cin>>N>>W;
    for (long long int i = 1; i <= N; i++)
    {
        cin>>w[i]>>v[i];
    }
    dfs(1,0,0);
    cout<<res<<endl;
}

解き方2. 動的計画法

まずすべての価値の和を$${S}$$とします。
ここで$${i}$$番目まで見て、価値が$${x}$$の時の重量の和の最小($${dp_{i,x}}$$)が$${0\le x\le S}$$についてわかっているとします。
この時、$${i+1}$$番目まで見て、価値が$${x}$$の時の重量の和の最小($${dp_{i,x}}$$)が$${0\le x\le S}$$について求められます。
今回の$${dp}$$配列の初期化は$${dp_{0,0}}$$のみ$${0}$$でそれ以外十分大きな数$${W+1}$$などにしておきましょう。

遷移1.絶対に荷物をナップサックに入れない

今$${i+1}$$番目の荷物をナップサックに入れなかったとしましょう。
この時は

$$
dp_{i+1,x}=dp_{i,x}\ \ \ (0 \le x \le S)
$$

になります。

遷移2.絶対に荷物をナップサックに入れる

今$${i+1}$$番目の荷物をナップサックに入れるとしましょう。
この時は

$$
dp_{i+1,x}=dp_{i,x-v_{i+1}}+w_{i+1}\ \ \ (v_{i+1}\le x\le S)
$$

になります。

遷移3.荷物をナップサックに入れるか自由

今$${i+1}$$番目の荷物をナップサックに入れるか自由としましょう。
この時は遷移1,2を合わせたもので

$$
\begin{align}
&dp_{i+1,x}=dp_{i,x}\ \ \ (0 \le x < v_{i+1})\\
&dp_{i+1,x}=\min(dp_{i,x},dp_{i,x-v_{i+1}}+w_{i+1})\ \ \ (v_{i+1}\le x\le S)
\end{align}
$$

になります。
minをとっているのは、$${dp}$$の定義が最小なためです。
この遷移の計算量は$${O(S)}$$になります。
これを繰り返して$${N}$$までやっても、計算量は$${O(NS)}$$で十分小さいです。
定義から$${dp_{N,x}\le W}$$を満たす最大の$${x}$$が答えになります。

実際のコードは以下のようになります。
$${i}$$周りについて少し説明とは異なりますが……。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long int N,W,S=0,res=0;
long long int w[501],v[501];

int main() {
    cin>>N>>W;
    for (long long int i = 1; i <= N; i++)
    {
        cin>>w[i]>>v[i];
        S+=v[i];
    }
    vector<vector<long long int>>dp(N+1,vector<long long int>(S+1,W+1));
    dp[0][0]=0;
    for (long long int i = 1; i <= N; i++)
    {
        for (long long int x = 0; x <= S; x++)
        {
            if(x-v[i]<0){
                dp[i][x]=dp[i-1][x];
            }else{
                dp[i][x]=min(dp[i-1][x],dp[i-1][x-v[i]]+w[i]);
            }
        }
    }
    for (long long int x = S; x >= 0 ; x--)
    {
        if(dp[N][x]<=W){
            cout<<x<<endl;
            return 0;
        }
    }
}