基本的な動的計画法(01-ナップサック)

はじめに

01-ナップサック問題とは何なのかという話をしていきたいと思います。

問題内容

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

制約

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

解き方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. 動的計画法

ここで$${i}$$番目まで見て、重さが$${x}$$以下の時の価値の和の最大($${dp_{i,x}}$$)が$${0\le x\le W}$$についてわかっているとします。
この時、$${i+1}$$番目まで見て、重さが$${x}$$以下の時の価値の和の最大($${dp_{i+1,x}}$$)が$${0\le x\le W}$$について求められます。

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

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

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

になります。

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

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

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

になります。

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

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

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

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

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

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

long long int N,W,res=0;
long long int w[501],v[501],dp[501][10001]={};

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