01-ナップサック(重量・価値が高い場合)

はじめに

問題は前回(基本的な動的計画法(価値が高い場合の01-ナップサック))と同じで制約が異なります。

問題内容

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

制約

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

解き方1. DFSで全探索

それぞれの荷物について入れるかどうか探索していきます。
計算量は$${O(2^N)}$$でかなり厳しい。
とはいえ、なんか頑張ればいける気がします。

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

long long int N,W,res=0;
long long int w[37],v[37];
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. 半分全列挙

前半分と後ろ半分で別々に全探索し、そのマージを二分探索で行います。
計算量は$${O(N2^{N/2})}$$で十分高速です。
例えば、前半分の結果の一つが$${(重量,価値)=(x_0,y_0)}$$の時、後半の結果として許される重量は$${W-x_0}$$です。
ここで、後半の結果のうち$${W-x_0}$$以下の重量で最大価値のものを選べば最適です。
これは、価値について累積Maxをとっておき二分探索で最大重量のものを選べばよいです。

実際のコードは以下のようになります。
少し説明とは異なりますが……。

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

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

int main() {
    cin>>N>>W;
    for (long long int i = 0; i < N; i++)
    {
        cin>>w[i]>>v[i];
    }
    long long int half=N/2;
    //前半分を計算(bit全探索)
    vector<pair<long long int,long long int>>vec1;
    for (long long int i = 0; i < (1LL<<half); i++)
    {
        long long int w_sum=0,v_sum=0;
        for (long long int j = 0; j < half; j++)
        {
            if(i&(1LL<<j)){
                w_sum += w[j];
                v_sum += v[j];
            }
        }
        if(w_sum<=W){
            vec1.push_back({w_sum,v_sum});
        }
    }

    //後ろ半分を計算(bit全探索)
    vector<pair<long long int,long long int>>vec2;
    for (long long int i = 0; i < (1LL<<(N-half)); i++)
    {
        long long int w_sum=0,v_sum=0;
        for (long long int j = 0; j < (N-half); j++)
        {
            if(i&(1LL<<j)){
                w_sum += w[j+half];
                v_sum += v[j+half];
            }
        }
        if(w_sum<=W){
            vec2.push_back({w_sum,v_sum});
        }
    }
    //sortして価値について累積Max(次の二分探索で利用する)
    sort(vec2.begin(),vec2.end());
    for (long long int i = 1; i < vec2.size(); i++)
    {
        vec2[i].second=max(vec2[i-1].second,vec2[i].second);
    }

    //前半すべてについて、後半どこまで選べるかを二分探索
    for (long long int i = 0; i < vec1.size(); i++)
    {
        long long int not_over=-1,over=vec2.size(),mid;
        while(over-not_over>1){
            mid=(over+not_over)/2;
            if(vec1[i].first+vec2[mid].first<=W){
                not_over=mid;
            }else{
                over=mid;
            }
        }
        if(not_over!=-1)res=max(res,vec1[i].second+vec2[not_over].second);
    }
    
    cout<<res<<endl;
}