非常に長い解説になっています メモ化再帰は使いません
1.はじめに
- 非常に長いので先にもっと簡単でわかりやすく短い解説を探して読んだほうが良いです
- 「1次元DPならギリギリ理解できるような気がするけどナップザックDPはマジで謎！！！」みたいな競プロer向けの記事です
- 競プロer向けなのでソースコードは適当です(特にPythonは競プロer向けだとしても滅茶苦茶な書き方の可能性があります すみません！！！)
2.前提知識(知ってたら飛ばしてOK)
Valueがintやlong longのとき、まだ存在しないKeyに[]でアクセスした場合、Valueが0である要素が新しく作られます。*1
例えば、
#include <bits/stdc++.h>
using namespace std;
int main(){
map<int,int> mp;
cout << mp[10] << endl;
mp[100]+=5;
cout << mp[100] << endl;
}
を実行すると
0
5
が出力されます。
配列の中身をすべて舐めることができます ぺろぺろ
autoを使うことでいちいちvectorを宣言するときに使った型を書かなくて済みます。
例えば、
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int> v={10,20,30};
for(auto i:v){
cout << i << endl;
}
vector<pair<int,int>> vp={{3,6},{4,8},{5,10000}};
for(auto i:vp){
cout << i.first << " " << i.second << endl;
}
}
を実行すると
10
20
30
3 6
4 8
5 10000
が出力されます。(参照をつけたほうが嬉しいときもあるけど説明が面倒なので省略！)
pairの方は構造化束縛(autoでいい感じに受け取れる機能)というのを使うと
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<pair<int,int>> vp={{3,6},{4,8},{5,10000}};
for(auto [k,v]:vp){
cout << k << " " << v << endl;
}
}
と書くことができます。
mapでも同じことができます。(中身がpair<Key,Value>なのに注意！) 例えば
#include <bits/stdc++.h>
using namespace std;
int main(){
map<int,int> mp;
mp[3]=6;
mp[4]=8;
mp[5]=10000;
for(auto [k,v]:mp){
cout << k << " " << v << endl;
}
}
と書くことができます。楽でよいですね。
Pythonista向け
- Pythonの基本的な文法(ABCのBが解けるかつdictが使えるくらい？基準がよくわかりません、すみません… 知らない文法が出てきたら適宜検索してください)
- defaultdict
dictでKeyが存在するかどうかの分岐を書くのが面倒なのでこの記事ではdefaultdictを使います。
例えば、
from collections import defaultdict
d=defaultdict(int)
d[3]=5
d[4]+=8
d[5]=max(d[5],10000)
for k,v in d.items():
print(k,v)
を実行すると
3 5
4 8
5 10000
が出力されます。
最初にintを渡しておいて*2存在しないKeyにアクセスするとValueが0の要素が新しく作られます。*3
+=とかmaxとかを何も考えずに使えてよいですね。
3.ナップザックDPを解く
とりあえず、この記事の目標をEDPC-Dを解くことにします。(問題はリンク先で確認してください)
(以下、C++のソースコードはGCC、PythonのソースコードはPyPy3で提出することとします)
3-1.全探索
いきなりDPだ！！！としてもよくわからないので、とりあえず全探索を考えましょう。
まず、品物の選び方は何通りでしょうか。品物iについて考えると、iを選ぶ場合と選ばない場合の2通りがあります。品物は全部で
個あるので、選び方は
通りあります。*4
こういうのはbit全探索だ！！！と思ってる人もいると思うんですが、とりあえず品物iを選ぶ、選ばないの2通りを前から考えていく実装をすることにします。
実装(C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,W;
cin >> N >> W;
vector<int> w(N),v(N);
for(int i=0;i<N;i++){
cin >> w[i] >> v[i];
}
vector<pair<int,long long>> s;
s.push_back({0,0});
for(int i=0;i<N;i++){
vector<pair<int,long long>> new_s;
for(auto [sum_w,sum_v]:s){
new_s.push_back({sum_w,sum_v});
new_s.push_back({sum_w+w[i],sum_v+v[i]});
}
s=new_s;
}
long long ans=0;
for(auto [sum_w,sum_v]:s){
if(sum_w<=W){
ans=max(ans,sum_v);
}
}
cout << ans << endl;
}
C++er向け補足：重さの総和が最大なのはすべての品物を選び、かつすべての品物の重さが最大のときなので、
となりintに収まり、重さの総和が最大なのはすべての品物を選び、かつすべての品物の重さが最大のときなので、最大で
となりintには収まらずlong longに収まります。
実装(Python)
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
w[i],v[i]=map(int,input().split())
s=[]
s.append((0,0))
for i in range(N):
new_s=[]
for sum_w,sum_v in s:
new_s.append((sum_w,sum_v))
new_s.append((sum_w+w[i],sum_v+v[i]))
s=new_s[:]
ans=0
for sum_w,sum_v in s:
if sum_w<=W:
ans=max(ans,sum_v)
print(ans)
(以下、品物の添字を0-indexed*5とします)
実装方針としては、あり得る(重さの総和,価値の総和)のペアを配列s*6で持って、どんどん更新していく感じです。
品物iを取らない場合、(重さの総和,価値の総和)は変化しません。
品物iを取る場合、(重さの総和,価値の総和)は(重さの総和+
,価値の総和+
)に変化します。
(ちなみに、このように、AからBへ更新していくことを「遷移する」といいます。*7
「遷移」という言葉は使いやすいので覚えておくとよいです。*8
AからBへ更新していくときのAを遷移元、Bを遷移先と呼ぶことにします。
)
最終的に、品物の選び方がすべてsに入っているので、重さの総和が
以下である選び方のうち、価値の総和が最大であるものを出力します。
(sを更新するのがよくわからない人は次の実装例も見ながら読んでみてください)
これを提出すると、TLEになります。
さっき品物の選び方は通りと書きました。ということは、new_sに値を突っ込む回数が回になっています。
のとき
となり、これは余裕でTLEします。
ここで、少し実装を変えます。sをnew_sで更新するのも良いのですが、いわゆるナップザックDPの形に近づけます。
実装(C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,W;
cin >> N >> W;
vector<int> w(N),v(N);
for(int i=0;i<N;i++){
cin >> w[i] >> v[i];
}
vector<vector<pair<int,long long>>> s(N+1);
s[0].push_back({0,0});
for(int i=0;i<N;i++){
for(auto [sum_w,sum_v]:s[i]){
s[i+1].push_back({sum_w,sum_v});
s[i+1].push_back({sum_w+w[i],sum_v+v[i]});
}
}
long long ans=0;
for(auto [sum_w,sum_v]:s[N]){
if(sum_w<=W){
ans=max(ans,sum_v);
}
}
cout << ans << endl;
}
実装(Python)
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
w[i],v[i]=map(int,input().split())
s=[[] for i in range(N+1)]
s[0].append((0,0))
for i in range(N):
for sum_w,sum_v in s[i]:
s[i+1].append((sum_w,sum_v))
s[i+1].append((sum_w+w[i],sum_v+v[i]))
ans=0
for sum_w,sum_v in s[N]:
if sum_w<=W:
ans=max(ans,sum_v)
print(ans)
やっていることはあまり変わりません。new_sを用意したりsを更新したりするのが面倒なので、最初に可変長配列を
個用意しておいて、sからnew_sではなくs[i]からs[i+1]に対して更新しているだけです。
このとき、s[i]は品物iよりも前の品物の選び方であり得る(品物の重さの総和,品物の価値の総和)が入っています。半開区間
*9に含まれる品物の選び方と捉えることもできます。
最終的に、品物の選び方がすべてs[N]に入ります。(品物は存在しませんが、品物
から品物
までの選び方が入っていると考えることができます)
3-2.工夫①(範囲の工夫)
ここから、どんどん探索を改善していきます。
まず、答えとしてあり得る選び方は重さの総和が以下なので、重さの総和がを超えるような選び方を持っておく必要はありません。これを実装すると、
実装(C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,W;
cin >> N >> W;
vector<int> w(N),v(N);
for(int i=0;i<N;i++){
cin >> w[i] >> v[i];
}
vector<vector<pair<int,long long>>> s(N+1);
s[0].push_back({0,0});
for(int i=0;i<N;i++){
for(auto [sum_w,sum_v]:s[i]){
s[i+1].push_back({sum_w,sum_v});
if(sum_w+w[i]<=W){
s[i+1].push_back({sum_w+w[i],sum_v+v[i]});
}
}
}
long long ans=0;
for(auto [sum_w,sum_v]:s[N]){
ans=max(ans,sum_v);
}
cout << ans << endl;
}
実装(Python)
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
w[i],v[i]=map(int,input().split())
s=[[] for i in range(N+1)]
s[0].append((0,0))
for i in range(N):
for sum_w,sum_v in s[i]:
s[i+1].append((sum_w,sum_v))
if sum_w+w[i]<=W:
s[i+1].append((sum_w+w[i],sum_v+v[i]))
ans=0
for sum_w,sum_v in s[N]:
ans=max(ans,sum_v)
print(ans)
こうなります。品物iを選ばない場合はsum_wが増えないので以下か調べなくてOKです。
これを提出すると、TLEになります。
よく考えると、が大きいかつが小さいときは、あまりこの工夫は効きません。例えば、、
、がすべて
のとき、どんな選び方でも重さの総和は
以下なので、すべての更新がif文を貫通します。
3-3.工夫②(持つ状態の工夫)
ここで、一度sの中身を見てみましょう。
3 100
2 3
2 4
4 4
のような入力でのsの中身を出力してみます。
(↓これは適当にsの中身を出力するソースコードなので真面目に読まなくてよいです)
実装(C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,W;
cin >> N >> W;
vector<int> w(N),v(N);
for(int i=0;i<N;i++){
cin >> w[i] >> v[i];
}
vector<vector<pair<int,long long>>> s(N+1);
s[0].push_back({0,0});
for(int i=0;i<N;i++){
for(auto [sum_w,sum_v]:s[i]){
s[i+1].push_back({sum_w,sum_v});
if(sum_w+w[i]<=W){
s[i+1].push_back({sum_w+w[i],sum_v+v[i]});
}
}
}
for(int i=0;i<=N;i++){
cout << i << ":";
for(auto [sum_w,sum_v]:s[i]){
cout << "(" << sum_w << "," << sum_v << ") ";
}
cout << endl;
}
}
実装(Python)
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
w[i],v[i]=map(int,input().split())
s=[[] for i in range(N+1)]
s[0].append((0,0))
for i in range(N):
for sum_w,sum_v in s[i]:
s[i+1].append((sum_w,sum_v))
if sum_w+w[i]<=W:
s[i+1].append((sum_w+w[i],sum_v+v[i]))
for i in range(N+1):
print(i,end=":")
for sum_w,sum_v in s[i]:
print("("+str(sum_w)+","+str(sum_v)+")",end=" ")
print()
Pythonista向け補足：C++に寄せて書こうとしたら大変なことになってしまいました 実際にsの中身を見たいときはprint(s)とかでよいと思います
すると、
0:(0,0)
1:(0,0) (2,3)
2:(0,0) (2,4) (2,3) (4,7)
3:(0,0) (4,4) (2,4) (6,8) (2,3) (6,7) (4,7) (8,11)
のような出力になります。(i:(x,y)…はs[i]に入っているペアが(重さの総和がx,価値の総和がy)…であることを表しています)
よく見ると、(4,4)と(4,7)、(2,4)と(2,3)のように、重さが同じで価値のみが異なるペアが入っています。
さて、本当に(4,4)や(2,3)は必要でしょうか。
重さの総和が同じなら、価値の総和が大きい方がお得です。
つまり、s[i]には、同じ重さならば、一番価値の総和が大きいペアしか必要ありません。
一応雑に証明してみます。(読み飛ばしてもOK)
雑証明
(重さと価値に「の総和」を付けるとごちゃごちゃしたのでここだけ外れています すみません)
から遷移して最終的にs[N]に入っている、品物の選び方としてあり得る(重さ,価値)をから遷移した解とする。
から遷移した解のうち、一番価値が高いものをから遷移した最適解とする。
命題：
s[i]に(重さ,価値)が
である2つが入っていた場合、
から遷移した最適解の価値は、
から遷移した最適解の価値を超えない。
証明：
から遷移した最適解を
とする。この最適解の価値は
である。
からに遷移しているので、重さが
、価値が
増えるような遷移が存在する。
ここで、
より
なのでから同じ遷移をさせることができ、
がから遷移した解として存在する。この解の価値は
である。
より、
なので、
となり、から遷移した最適解の価値がから遷移した解の価値を超えない。
よって、から遷移した最適解の価値は、から遷移した最適解の価値を超えない。Q.E.D.
(思ったより長くなってしまった… コンテスト中は同じ重さなら価値が高い方が嬉しいよね～くらいでよいです)
結局、s[i]には、同じ重さならば、一番価値が大きいペアしか必要ないので、c++ならmap、Pythonならdefaultdictなどを使って(重さの総和,その重さの総和のものの価値の総和の最大値)のようなペアを作るように実装してみます。
実装(C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,W;
cin >> N >> W;
vector<int> w(N),v(N);
for(int i=0;i<N;i++){
cin >> w[i] >> v[i];
}
vector<map<int,long long>> s(N+1);
s[0][0]=0;
for(int i=0;i<N;i++){
for(auto [sum_w,sum_v]:s[i]){
s[i+1][sum_w]=max(s[i+1][sum_w],sum_v);
if(sum_w+w[i]<=W){
s[i+1][sum_w+w[i]]=max(s[i+1][sum_w+w[i]],sum_v+v[i]);
}
}
}
long long ans=0;
for(auto [sum_w,sum_v]:s[N]){
ans=max(ans,sum_v);
}
cout << ans << endl;
}
実装(Python)
from collections import defaultdict
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
w[i],v[i]=map(int,input().split())
s=[defaultdict(int) for i in range(N+1)]
s[0][0]=0
for i in range(N):
for sum_w,sum_v in s[i].items():
s[i+1][sum_w]=max(s[i+1][sum_w],sum_v)
if sum_w+w[i]<=W:
s[i+1][sum_w+w[i]]=max(s[i+1][sum_w+w[i]],sum_v+v[i])
ans=0
for sum_w,sum_v in s[N].items():
ans=max(ans,sum_v)
print(ans)
ナップザックDPっぽくなってきましたね！！！
s[i][sum_w]=品物iよりも前の品物の選び方で重さの総和がsum_wのものの価値の総和の最大値としています。
品物iを取らない、取るどちらの遷移もそれまでの価値の最大値を超える場合に行うとすると、価値の最大値がいい感じに求まります。
これを提出すると、C++なら(たぶん)TLEします。そんな…
Pythonならギリギリで通るかもしれません。自分は通りました。(Submission #43903387 - Educational DP Contest)
すみません、実は最初は計算量評価を間違えていて割と余裕でACすると思っていたので←は？？？ このあたりの文章が怪しくなっています
この実装は、品物iよりも前の品物の選び方の、(重さの総和,その重さの総和のものの価値の総和の最大値)が突っ込まれたものをs[i]としていて、品物の重さはを超えないように実装しているので、s[i]の要素数はを超えません。これが個あり、s[i]の要素一つ一つに対して
(a)それぞれの要素に対して
(b)遷移できるかどうか調べています。
計算量は、C++なら、(a)は
、s[i+1]の要素も個以下なので(b)もとなり*10、s[i]一つにつき
であり、これを回行うので、全体で
となり、これは、だと実行時間制限である2secに間に合わなさそうです。(参考:
)
Pythonなら(a)も(b)も平均*11
*12なので、s[i]一つにつき平均
、全体で平均
となり、これは、でも実行時間制限である2secに間に合いそうですが、(参考:)平均計算量なので、ギリギリでACしたりTLEしたりします。
ここで、s[i]に入っている重みがを超えない、つまり以上以下なので、C++のmapやPythonのdefaultdictではなくただの大きさ
の配列を使って実装することができます。*13
ただし、そのまま配列を使ってsum_wをからまで動かすと存在しないはずの(重さの総和,価値の総和)から遷移してしまう*14ので、うまく回避しなければいけません。
実装方針としてはおおよそ2通りあり、1つ目は存在しない遷移をさせない、
実装(C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,W;
cin >> N >> W;
vector<int> w(N),v(N);
for(int i=0;i<N;i++){
cin >> w[i] >> v[i];
}
vector<vector<long long>> s(N+1,vector<long long>(W+1,-1));
s[0][0]=0;
for(int i=0;i<N;i++){
for(int sum_w=0;sum_w<=W;sum_w++){
long long sum_v=s[i][sum_w];
if(sum_v==-1) continue;
s[i+1][sum_w]=max(s[i+1][sum_w],sum_v);
if(sum_w+w[i]<=W){
s[i+1][sum_w+w[i]]=max(s[i+1][sum_w+w[i]],sum_v+v[i]);
}
}
}
long long ans=0;
for(int sum_w=0;sum_w<=W;sum_w++){
long long sum_v=s[N][sum_w];
ans=max(ans,sum_v);
}
cout << ans << endl;
}
実装(Python)
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
w[i],v[i]=map(int,input().split())
s=[[-1]*(W+1) for i in range(N+1)]
s[0][0]=0
for i in range(N):
for sum_w in range(W+1):
sum_v=s[i][sum_w]
if sum_v==-1:
continue
s[i+1][sum_w]=max(s[i+1][sum_w],sum_v)
if sum_w+w[i]<=W:
s[i+1][sum_w+w[i]]=max(s[i+1][sum_w+w[i]],sum_v+v[i])
ans=0
for sum_w in range(W+1):
sum_v=s[N][sum_w]
ans=max(ans,sum_v)
print(ans)
とする実装です。
sを-1で初期化しておくことで、存在しない遷移元(例えば(0,1)など)から遷移しないようにcontinueさせることができます。価値の総和は負にならないので、遷移先でmaxを取るとmax(-1,価値の総和)=価値の総和となり、うまく動きます。
もちろん-1ではなく価値の総和の最小値である0より小さい数であればどれを使って実装してもよいです。
2つ目は存在しない遷移をしても答えに影響しない、
実装(C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,W;
cin >> N >> W;
vector<int> w(N),v(N);
for(int i=0;i<N;i++){
cin >> w[i] >> v[i];
}
long long INF=1e18;
vector<vector<long long>> s(N+1,vector<long long>(W+1,-INF));
s[0][0]=0;
for(int i=0;i<N;i++){
for(int sum_w=0;sum_w<=W;sum_w++){
long long sum_v=s[i][sum_w];
s[i+1][sum_w]=max(s[i+1][sum_w],sum_v);
if(sum_w+w[i]<=W){
s[i+1][sum_w+w[i]]=max(s[i+1][sum_w+w[i]],sum_v+v[i]);
}
}
}
long long ans=0;
for(int sum_w=0;sum_w<=W;sum_w++){
long long sum_v=s[N][sum_w];
ans=max(ans,sum_v);
}
cout << ans << endl;
}
実装(Python)
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
w[i],v[i]=map(int,input().split())
INF=10**18
s=[[-INF]*(W+1) for i in range(N+1)]
s[0][0]=0
for i in range(N):
for sum_w in range(W+1):
sum_v=s[i][sum_w]
s[i+1][sum_w]=max(s[i+1][sum_w],sum_v)
if sum_w+w[i]<=W:
s[i+1][sum_w+w[i]]=max(s[i+1][sum_w+w[i]],sum_v+v[i])
ans=0
for sum_w in range(W+1):
sum_v=s[N][sum_w]
ans=max(ans,sum_v)
print(ans)
とする実装です。
この問題の答えは必ず0以上になる*15ので、最初にいくら価値を足しても答えになり得ない値(の上限が、の上限が
なので、
よりも小さい値)で配列を初期化してあげると、いちいちcontinueしなくても余計な遷移を考えなくて済みます。ここではINF=
として-INFで初期化をしています。
maxを取るくだりは1つ目の実装と同じようにmax(-INF,価値の総和)=価値の総和となり、うまく動きます。
(実はこの問題の場合初期化の値は0以下であれば大丈夫なのですが、その話は後で…)
どちらの実装でも、C++、Python関係なく計算量はになります。
これを提出すると、無事ACすることができます！！！やった～～～～～～～～
2つ目の実装はcontinueを書かなくて済み楽なので、この後もこの2つ目のような実装をすることにします。
結局、s[i][j]=「品物iよりも前の品物の選び方で重さの総和がjのものの価値の総和の最大値」なので、sum_wをjにして、
実装(C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,W;
cin >> N >> W;
vector<int> w(N),v(N);
for(int i=0;i<N;i++){
cin >> w[i] >> v[i];
}
long long INF=1e18;
vector<vector<long long>> s(N+1,vector<long long>(W+1,-INF));
s[0][0]=0;
for(int i=0;i<N;i++){
for(int j=0;j<=W;j++){
long long sum_v=s[i][j];
s[i+1][j]=max(s[i+1][j],sum_v);
if(j+w[i]<=W){
s[i+1][j+w[i]]=max(s[i+1][j+w[i]],sum_v+v[i]);
}
}
}
long long ans=0;
for(int j=0;j<=W;j++){
long long sum_v=s[N][j];
ans=max(ans,sum_v);
}
cout << ans << endl;
}
実装(Python)
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
w[i],v[i]=map(int,input().split())
INF=10**18
s=[[-INF]*(W+1) for i in range(N+1)]
s[0][0]=0
for i in range(N):
for j in range(W+1):
sum_v=s[i][j]
s[i+1][j]=max(s[i+1][j],sum_v)
if j+w[i]<=W:
s[i+1][j+w[i]]=max(s[i+1][j+w[i]],sum_v+v[i])
ans=0
for j in range(W+1):
sum_v=s[N][j]
ans=max(ans,sum_v)
print(ans)
sum_vをいちいち作らずそのままアクセスして、
実装(C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,W;
cin >> N >> W;
vector<int> w(N),v(N);
for(int i=0;i<N;i++){
cin >> w[i] >> v[i];
}
long long INF=1e18;
vector<vector<long long>> s(N+1,vector<long long>(W+1,-INF));
s[0][0]=0;
for(int i=0;i<N;i++){
for(int j=0;j<=W;j++){
s[i+1][j]=max(s[i+1][j],s[i][j]);
if(j+w[i]<=W){
s[i+1][j+w[i]]=max(s[i+1][j+w[i]],s[i][j]+v[i]);
}
}
}
long long ans=0;
for(int j=0;j<=W;j++){
ans=max(ans,s[N][j]);
}
cout << ans << endl;
}
実装(Python)
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
w[i],v[i]=map(int,input().split())
INF=10**18
s=[[-INF]*(W+1) for i in range(N+1)]
s[0][0]=0
for i in range(N):
for j in range(W+1):
s[i+1][j]=max(s[i+1][j],s[i][j])
if j+w[i]<=W:
s[i+1][j+w[i]]=max(s[i+1][j+w[i]],s[i][j]+v[i])
ans=0
for j in range(W+1):
ans=max(ans,s[N][j])
print(ans)
変数名をsからdpにすると、
実装(C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,W;
cin >> N >> W;
vector<int> w(N),v(N);
for(int i=0;i<N;i++){
cin >> w[i] >> v[i];
}
long long INF=1e18;
vector<vector<long long>> dp(N+1,vector<long long>(W+1,-INF));
dp[0][0]=0;
for(int i=0;i<N;i++){
for(int j=0;j<=W;j++){
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
if(j+w[i]<=W){
dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
}
}
}
long long ans=0;
for(int j=0;j<=W;j++){
ans=max(ans,dp[N][j]);
}
cout << ans << endl;
}
実装(Python)
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
w[i],v[i]=map(int,input().split())
INF=10**18
dp=[[-INF]*(W+1) for i in range(N+1)]
dp[0][0]=0
for i in range(N):
for j in range(W+1):
dp[i+1][j]=max(dp[i+1][j],dp[i][j])
if j+w[i]<=W:
dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i])
ans=0
for j in range(W+1):
ans=max(ans,dp[N][j])
print(ans)
となり、見たことのあるナップザックDPの実装になりました！！！おめでとうございます！！！
3-4.おまけ？
さて、さっき「見たことのあるナップザックDPの実装になりました」と書きましたが、このタイプの実装ではない、最後がdp[N][W]を出力するだけの実装を見たことがある人もいるのではないでしょうか。
この場合、dp[i][j]=「品物iよりも前の品物の選び方で重さの総和がj以下のものの価値の総和の最大値」として考えたくなります。
この考え方をすると、dp[0][j]はすべて0で初期化したほうがよさそうです。
dpを定義通りに更新すると、
実装(C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,W;
cin >> N >> W;
vector<int> w(N),v(N);
for(int i=0;i<N;i++){
cin >> w[i] >> v[i];
}
long long INF=1e18;
vector<vector<long long>> dp(N+1,vector<long long>(W+1,-INF));
for(int j=0;j<=W;j++){
dp[0][j]=0;
}
for(int i=0;i<N;i++){
for(int j=0;j<=W;j++){
for(int k=j;k<=W;k++){
dp[i+1][k]=max(dp[i+1][k],dp[i][j]);
}
for(int k=j+w[i];k<=W;k++){
dp[i+1][k]=max(dp[i+1][k],dp[i][j]+v[i]);
}
}
}
cout << dp[N][W] << endl;
}
実装(Python)
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
w[i],v[i]=map(int,input().split())
INF=10**18
dp=[[-INF]*(W+1) for i in range(N+1)]
for j in range(W+1):
dp[0][j]=0
for i in range(N):
for j in range(W+1):
for k in range(j,W+1):
dp[i+1][k]=max(dp[i+1][k],dp[i][j])
for k in range(j+w[i],W+1):
dp[i+1][k]=max(dp[i+1][k],dp[i][j]+v[i])
print(dp[N][W])
となります。
dp[i][j]=「品物iよりも前の品物の選び方で重さの総和がj以下のものの価値の総和の最大値」なので、dp[i][j]から品物iを取る取らないどちらかを選んで、重さの総和がXになったとき、重さの総和がX以上であるすべてのkに対して、dp[i][j]からdp[i+1][k]への遷移をしなければいけません。
このDPはたしかに正しい答えを出力しますが、このままでは
*16になってしまい、TLEしてしまいます。(参考：、
のとき
)
実は、3-3の最後の実装のように、dp[i][j]からは取る、取らないそれぞれ1回ずつの遷移だけで大丈夫です。
実装(C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,W;
cin >> N >> W;
vector<int> w(N),v(N);
for(int i=0;i<N;i++){
cin >> w[i] >> v[i];
}
long long INF=1e18;
vector<vector<long long>> dp(N+1,vector<long long>(W+1,-INF));
for(int j=0;j<=W;j++){
dp[0][j]=0;
}
for(int i=0;i<N;i++){
for(int j=0;j<=W;j++){
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
if(j+w[i]<=W){
dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
}
}
}
cout << dp[N][W] << endl;
}
実装(Python)
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
w[i],v[i]=map(int,input().split())
INF=10**18
dp=[[-INF]*(W+1) for i in range(N+1)]
for j in range(W+1):
dp[0][j]=0
for i in range(N):
for j in range(W+1):
dp[i+1][j]=max(dp[i+1][j],dp[i][j])
if j+w[i]<=W:
dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i])
print(dp[N][W])
なぜこの実装でうまくDPが回るのでしょうか？とりあえず答えだけ考えてみましょう。
(どっちがどっちのDPかわからなくなるので、3-3の最後のようなDPの変数名を
、今書いたdp[N][W]を出力するDPの変数名を
とします)
3-3のようなDPでは、最後に![s[N][j](0\leqq j\leqq W)](https://chart.apis.google.com/chart?cht=tx&chl=s%5BN%5D%5Bj%5D%280%5Cleqq%20j%5Cleqq%20W%29)
を全探索して最大の値を持ってきていました。
ここで、最大の値が入った場所を![s[N][x]](https://chart.apis.google.com/chart?cht=tx&chl=s%5BN%5D%5Bx%5D)
とします。
このとき、![s[0][0]](https://chart.apis.google.com/chart?cht=tx&chl=s%5B0%5D%5B0%5D)
からいい感じに遷移をしてに値が入っているはずです。
今書いたDPは、最初に![dp[0][j](0\leqq j\leqq W)](https://chart.apis.google.com/chart?cht=tx&chl=dp%5B0%5D%5Bj%5D%280%5Cleqq%20j%5Cleqq%20W%29)
をで初期化しました。ということは、![dp[0][W-x]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5B0%5D%5BW-x%5D)
*17からと同じような遷移をすると、![dp[N][W-x+x]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5BN%5D%5BW-x%2Bx%5D)
、つまり![dp[N][W]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5BN%5D%5BW%5D)
にの値が入っているはずです。
は最大の値だったので、maxを取っても別の値になることはありません。
よって、このDPでを答えとしても正しいことがわかりました。
とりあえず、答えは正しいことがわかりました。ではすべてのdp[i][j]は、本当にdpの定義、つまり「品物iよりも前の品物の選び方で重さの総和がj以下のものの価値の総和の最大値」になっているのでしょうか。
せっかくなのでまた雑証明をしたいと思います。(読み飛ばしてもOK)
雑証明
(前提として、3-4の最初に書いたTLEするDPが定義を満たすとしています 雑なので許して～)
補題：
広義単調増加である長さの数列
があり、
と定義される数列
がある。
このとき、は広義単調増加である。
証明：
なので
は
か
である。
のとき、
であるので、
である。
のとき、
であるので、である。
以上から、が、どちらでも
が成り立つ。よっては広義単調増加である。
命題：
![dp[i+1][k]=max(dp[i+1][k],dp[i][j])(j+1\leqq k\leqq W)](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D%5Bk%5D%3Dmax%28dp%5Bi%2B1%5D%5Bk%5D%2Cdp%5Bi%5D%5Bj%5D%29%28j%2B1%5Cleqq%20k%5Cleqq%20W%29)
![dp[i+1][k]=max(dp[i+1][k],dp[i][j]+v[i])(j+w[i]+1\leqq k\leqq W)](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D%5Bk%5D%3Dmax%28dp%5Bi%2B1%5D%5Bk%5D%2Cdp%5Bi%5D%5Bj%5D%2Bv%5Bi%5D%29%28j%2Bw%5Bi%5D%2B1%5Cleqq%20k%5Cleqq%20W%29)
どちらの遷移もする必要がない。
証明：
まず、数学的帰納法を用いて](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%5D%280%5Cleqq%20i%5Cleqq%20N%29)
はすべて広義単調増加であることを示す。
のとき、はで初期化されているので、![dp[i]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%5D)
は広義単調増加である。
が広義単調増加であると仮定する。
![0\leqq j\lt w[i]](https://chart.apis.google.com/chart?cht=tx&chl=0%5Cleqq%20j%5Clt%20w%5Bi%5D)
として![dp[i+1][j]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D%5Bj%5D)
を考える。
![w[i]\leqq j+w[i]](https://chart.apis.google.com/chart?cht=tx&chl=w%5Bi%5D%5Cleqq%20j%2Bw%5Bi%5D)
より、
![dp[i+1][j]=max(dp[i+1][j],dp[i][j])](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D%5Bj%5D%3Dmax%28dp%5Bi%2B1%5D%5Bj%5D%2Cdp%5Bi%5D%5Bj%5D%29)
の遷移しか存在しない。
の初期値は
なので、
![dp[i+1][j]=max(-10^{18},dp[i][j])](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D%5Bj%5D%3Dmax%28-10%5E%7B18%7D%2Cdp%5Bi%5D%5Bj%5D%29)
つまり
![dp[i+1][j]=dp[i][j]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D%5Bj%5D%3Ddp%5Bi%5D%5Bj%5D)
である。
は広義単調増加より、![dp[i+1][j](0\leqq j\lt w[i])](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D%5Bj%5D%280%5Cleqq%20j%5Clt%20w%5Bi%5D%29)
の範囲において広義単調増加である。
![w[i]\leqq j\leqq W](https://chart.apis.google.com/chart?cht=tx&chl=w%5Bi%5D%5Cleqq%20j%5Cleqq%20W)
としてを考える。
、
![dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D%5Bj%5D%3Dmax%28dp%5Bi%2B1%5D%5Bj%5D%2Cdp%5Bi%5D%5Bj-w%5Bi%5D%5D%2Bv%5Bi%5D%29)
の2つの遷移が存在する。
の初期値はなので、![dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i],-10^{18})](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D%5Bj%5D%3Dmax%28dp%5Bi%5D%5Bj%5D%2Cdp%5Bi%5D%5Bj-w%5Bi%5D%5D%2Bv%5Bi%5D%2C-10%5E%7B18%7D%29)
つまり
![dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D%5Bj%5D%3Dmax%28dp%5Bi%5D%5Bj%5D%2Cdp%5Bi%5D%5Bj-w%5Bi%5D%5D%2Bv%5Bi%5D%29)
である。*18
ここで、数列
を用意し、それぞれ
![A_{j-w[i]}=dp[i][j],B_{j-w[i]}=dp[i][j-w[i]]+v[i],C_{j-w[i]}=dp[i+1][j]](https://chart.apis.google.com/chart?cht=tx&chl=A_%7Bj-w%5Bi%5D%7D%3Ddp%5Bi%5D%5Bj%5D%2CB_%7Bj-w%5Bi%5D%7D%3Ddp%5Bi%5D%5Bj-w%5Bi%5D%5D%2Bv%5Bi%5D%2CC_%7Bj-w%5Bi%5D%7D%3Ddp%5Bi%2B1%5D%5Bj%5D)
とする。
は広義単調増加より、数列ともに広義単調増加である。
ここで、より、
であるから、補題より、数列は広義単調増加である。
よって、![dp[i+1][j](w[i]\leqq j\leqq W)](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D%5Bj%5D%28w%5Bi%5D%5Cleqq%20j%5Cleqq%20W%29)
の範囲において広義単調増加である。
![dp[i+1][w[i]-1]=dp[i][w[i]-1]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D%5Bw%5Bi%5D-1%5D%3Ddp%5Bi%5D%5Bw%5Bi%5D-1%5D)
、
![dp[i+1][w[i]]=max(dp[i][w[i]],dp[i][0]+v[i])](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D%5Bw%5Bi%5D%5D%3Dmax%28dp%5Bi%5D%5Bw%5Bi%5D%5D%2Cdp%5Bi%5D%5B0%5D%2Bv%5Bi%5D%29)
であり、
は広義単調増加から![dp[i][w[i]-1]\leqq dp[i][w[i]]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%5D%5Bw%5Bi%5D-1%5D%5Cleqq%20dp%5Bi%5D%5Bw%5Bi%5D%5D)
なので、
![dp[i+1][w[i]-1]\leqq dp[i+1][w[i]]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D%5Bw%5Bi%5D-1%5D%5Cleqq%20dp%5Bi%2B1%5D%5Bw%5Bi%5D%5D)
である。
これらから、
、
それぞれの範囲で広義単調増加であり、かつ
であるため、![dp[i+1]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D)
は広義単調増加である。
より、数学的帰納法から、は広義単調増加である。
の遷移について考える。
![dp[i][k]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%5D%5Bk%5D)
から![dp[i+1][k]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%2B1%5D%5Bk%5D)
への遷移が別に存在し、は広義単調増加より、![dp[i][j]\leqq dp[i][k]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%5D%5Bj%5D%5Cleqq%20dp%5Bi%5D%5Bk%5D)
なので、![dp[i][j]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%5D%5Bj%5D)
からへ遷移をする必要がない。
の遷移について考える。
![dp[i][k-w[i]]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%5D%5Bk-w%5Bi%5D%5D)
からへの遷移が別に存在し、は広義単調増加より、![dp[i][j]+v[i]\leqq dp[i][k-w[i]]+v[i]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Bi%5D%5Bj%5D%2Bv%5Bi%5D%5Cleqq%20dp%5Bi%5D%5Bk-w%5Bi%5D%5D%2Bv%5Bi%5D)
なので、からへ遷移をする必要がない。
以上から、
どちらの遷移もする必要がない。Q.E.D.
ところでこれこんなに証明長くなる？？？もっといい証明が思いついたら教えてください…
ということで(？)、すべてのdp[i][j]が定義を満たしていることがわかりました。
さて、雑証明を読んでくれた方ならすぐわかると思うのですが、このDPは-INFで初期化しなくても0以下の値で初期化すればOKです。(maxを取るところで遷移に影響しなければよいので)
dp[0][j]は0で初期化しないといけないので、配列をすべて0で初期化するのが一番楽です。
(よく考えると、dp[i][j]=「品物iよりも前の品物の選び方で重さの総和がj以下のものの価値の総和の最大値」で、どの品物までの選び方でも重さの総和が0であるような選び方が必ず存在する*19のですべて初期値が0でも大丈夫ですね うっかりしていました)
実装(C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,W;
cin >> N >> W;
vector<int> w(N),v(N);
for(int i=0;i<N;i++){
cin >> w[i] >> v[i];
}
vector<vector<long long>> dp(N+1,vector<long long>(W+1,0));
for(int i=0;i<N;i++){
for(int j=0;j<=W;j++){
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
if(j+w[i]<=W){
dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
}
}
}
cout << dp[N][W] << endl;
}
実装(Python)
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
w[i],v[i]=map(int,input().split())
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(N):
for j in range(W+1):
dp[i+1][j]=max(dp[i+1][j],dp[i][j])
if j+w[i]<=W:
dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i])
print(dp[N][W])
これはそれなりに短く書けるの解法です。
4.結局
(ナップザックDPだけ理解できればOK！という人はここで読むのをやめて大丈夫です)
結局、(ナップザックDPに限らず)DPで大事なのは初期化と遷移です。(当たり前)
こうやって状態をまとめると、この状態の最大値を見つけるにはこの状態の最大値とこの状態の最大値からの遷移だけすればよい！みたいな考え方ができるようになったら、たぶんどんどんDPの問題が解けるようになると思います。
逆に(？)、N次元DPをN次元配列だと意識する必要はそんなにありません。配列の次元は添字を管理するためだけのものであると考えた方が簡単になる場合が多いと思います。
もちろん、いちいち多次元配列を使わずに、C++のmapやPythonのdefaultdictなどで添字を管理することもできなくはないです。
例えば、3-4の一番最後の解法は、
実装(C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,W;
cin >> N >> W;
vector<int> w(N),v(N);
for(int i=0;i<N;i++){
cin >> w[i] >> v[i];
}
map<pair<int,int>,long long> dp;
for(int i=0;i<N;i++){
for(int j=0;j<=W;j++){
dp[{i+1,j}]=max(dp[{i+1,j}],dp[{i,j}]);
if(j+w[i]<=W){
dp[{i+1,j+w[i]}]=max(dp[{i+1,j+w[i]}],dp[{i,j}]+v[i]);
}
}
}
cout << dp[{N,W}] << endl;
}
実装(Python)
from collections import defaultdict
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
w[i],v[i]=map(int,input().split())
dp=defaultdict(int)
for i in range(N):
for j in range(W+1):
dp[(i+1,j)]=max(dp[(i+1,j)],dp[(i,j)])
if j+w[i]<=W:
dp[(i+1,j+w[i])]=max(dp[(i+1,j+w[i])],dp[(i,j)]+v[i])
print(dp[(N,W)])
と書くこともできます。(これはTLEします)
もちろん人々が多次元配列を使うのは、C++ならlogが落ちる、Pythonならtupleを使わなくて済み最悪計算量で抑えられる、かつ書きやすい(こっちは人によるかも？)からです。
しかし、N次元DPをN次元配列として意識しすぎて、表を書いて矢印を伸ばしてみたいなことをするよりは、遷移のみを考える、つまりどの添字からどの添字へどのように遷移するかだけを考えるほうが簡単な場合もあると思います。
5.練習問題
正直この文章をすべて理解出来たらABCのD問題くらいまでのDPは解説を理解できると思うので適当に解いてください(え？？？？？)
最初はこう書いてたんですけどさすがに無責任すぎるのでもう少し真面目に書きます！
D - Poisonous Full-Course
選出理由：この前自分が解いたばかりだったため状態を添字にするDPとしてよい例だったため
状態を添字にするDPです。状態は0と1で持つのが楽です。いい感じにdp[i][j]を自分で定義して解いてみましょう。
よくわからなかったら割と早めに解説を見ても大丈夫です。
D - Shift vs. CapsLock
選出理由：状態を添字にするDPとしてよい例だったため2、DPには色々と持たせることができるよい例だったため
DPが持つのは最小値と最大値だけじゃないということです。
この問題はグラフを使って解くこともできます。
E - Knapsack 2
選出理由：EDPC-Dの次の問題だったため
計算量に気を付けましょう！！！
dpをどう定義して何を持たせれば間に合うかを考える問題です。
よくわからなかったら割と早めに解説を見ても(検索しても)大丈夫です。
これナップザックDPを理解した直後にすんなり解ける人、いるのか？？？
お疲れさまでした！後は頑張って色んな問題を解きましょう！
6.雑談
ナップザックDPのわかりにくいところって計算量がナップザックの容量で抑えられるところだと思うんですよね
最後にmax(dp[N])を出力するタイプとdp[N][W]を出力するタイプがあるのもややこしそう
そもそも配るDPと貰うDPの2パターンがある時点でDPって難しいと思います
ところで最初PythonのコードをPythonで出していてなんでTLE！？！？となっていました
4.1：動的計画法の復習（ナップサック問題） - HackMDを読んでPyPyの存在を思い出しました Pythonを全然使っていないのがバレてしまう…
