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;
}
この記事が気に入ったらサポートをしてみませんか?