AOJ DPL 1.Combinatorial
はい。
http://judge.u-aizu.ac.jp/onlinejudge/topic.jsp?cid=DPL
A:Coin Changing Problem
C++11
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<queue> #include<algorithm> using namespace std; int main(){ int n,m; scanf("%d %d",&n,&m); vector<int> coin(m); for(auto&e:coin){ scanf("%d",&e); } //dp用のvector配列は0円から支払いのn円分まで用意 vector<int> dp_coin(n); //支払い枚数はコインの金種に必ず1円玉があるので //n円の支払いの最悪は1円玉をn枚使用する場合である //金種が1種類のみもあり得る //その場合はそのままn円を1円玉のみの支払いで解となる //dpテーブルはとりあえずn枚支払いを想定で埋める fill(dp_coin.begin(), dp_coin.end(), n); //n円の支払いを0枚にする? なるほどわからない dp_coin[n]=0; //金額の大きいn円のほうから1円ずつ減らして調べる for(int i=n;i>0;i--){ //支払い方法を探すループは金額の小さいコインから確認 //n円の支払いの最小枚数はn円-coin[j]円玉の金額の最小枚数が //分かればソレにcoin[j]円玉を使えばn円支払いの最小枚数と言えるはず for(int j=0;j<m;j++){ //0円より小さくなるマイナスの金額は対象外にする if(i>=coin[j]){ dp_coin[i-coin[j]]=min(dp_coin[i]+1,dp_coin[i-coin[j]]); } } } printf("%d\n",dp_coin[0]); return 0; }
はい。複数種類あるコインから特定金額の支払いを最小枚数で〜〜というのはDPではかなり典型問題のようです。AOJの問題文の解説の方にも書かれていますが金額の大きい方から使う貪欲法では最小枚数を選択することが出来ません。
ソース内のコメントは推測です。動的計画法を全く理解していないのでコメントは推測です。
B:0-1 Knapsack Problem
C++11
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<queue> #include<algorithm> using namespace std; int main(){ int N,W,v,w,ans=0; scanf("%d %d",&N,&W); //重さがdp[i]の時に価値が最大となるのを調べるdpテーブル vector<int> dp(W+1); //dpテーブルは全て0で初期化 fill(dp.begin(), dp.end(), 0); //荷物の価値vと重さwの入力データをN回受け取る for(int i=0;i<N;i++){ scanf("%d %d",&v,&w); //問題の制限での最大の重さWから入力で受け取った荷物の重さwの範囲で調べる for(int j=W-w;j>0;j--){ //入力で受け取った荷物を使ったほうが価値が高くなるかを比較する if(dp[j]!=0){ dp[j+w]=max(dp[j+w],dp[j]+v); } } //dpテーブルが0だったときはvで更新される dp[w]=max(dp[w],v); } //dpテーブルの最大値を出力 printf("%d\n",*max_element(dp.begin(),dp.end())); return 0; }
コメントは適当な推測です。間違っている可能性がかなり高いです。調べている流れとしては重さがW以下の時に価値が大きくなるかを調べています。また、今回はそれぞれの荷物を1度しか選べないです。入力データに同じ重さ、価値のものがあってもi番目の荷物を選べるのは1度だけです。そのために荷物を選び終わった後に重さがWではない場合があるかと思いますが、重さの総和がWを超えないときのことを調べているので問題無いと思います。多分。
C:Knapsack Problem
C++11
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<queue> #include<algorithm> using namespace std; int main(){ int N,W,v,w; scanf("%d %d",&N,&W); //制限の重さWまでのdpテーブルを用意して0埋めする vector<int> dp(W+1); fill(dp.begin(), dp.end(), 0); //入力を受け取りながら受け取った荷物の重さのとこを確認 for(int i=0;i<N;i++){ scanf("%d %d",&v,&w); dp[w]=max(dp[w],v); //よくわからない for(int j=0;j<W-w+1;j++){ if(dp[j]!=0){ dp[j+w]=max(dp[j+w],dp[j]+v); } } } //dpテーブルの最大値を出力 printf("%d\n",*max_element(dp.begin(),dp.end())); return 0; }
コメントは適当です。
D:Longest Increasing Subsequence
C++11
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<queue> #include<algorithm> using namespace std; int main(){ int n,a,chk=0,ans=0; int INF=(int)1e9; scanf("%d",&n); int dp[n]; fill(dp,dp+n, INF); vector<int> l(n); for(auto&e:l){ scanf("%d",&e); } for(int i=0;i<n;i++){ *lower_bound(dp,dp+n, l[i])=l[i]; } printf("%d\n",lower_bound(dp,dp+n, INF)-dp); return 0; }
AOJサイトの解説で不明なことがあったので質問ぶん投げた。