「AOJ Problem Set from DPL 問0～4」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
*Combinatorial - Coin Changing Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A
金額を払うのに必要な最小コイン枚数をDPで解く問題。
#include<stdio.h>
#include<vector>
int main(){
int n,m,memo[50001]={0};
scanf("%d %d",&n,&m);
int coin;
for(int i=0;i<m;i++){
scanf("%d",&coin);
for(int j=0;j+coin<=n;j++){
if(memo[j]==0&&j>0)continue;
if(memo[j+coin]==0||memo[j+coin]>memo[j]+1){
memo[j+coin]=memo[j]+1;
}
}
}
printf("%d\n",memo[n]);
}
*Combinatorial - 0-1 Knapsack Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B
重さ付きナップザック問題。
#include<stdio.h>
#include<vector>
int main(){
int n,W,memo[10001]={0};
scanf("%d %d",&n,&W);
int v,w,sum=0,ans=0;
while(n--){
scanf("%d %d",&v,&w);
if(sum+w>W)sum=W-w;
for(int j=sum;j>=0;j--){
if(memo[j+w]<memo[j]+v)memo[j+w]=memo[j]+v;
}
sum+=w;
}
for(int i=0;i<=W;i++)if(ans<memo[i])ans=memo[i];
printf("%d\n",ans);
}
*Combinatorial - Longest Increasing Subsequence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D
数列の中の最長増加部分列の長さをこたえる問題。
最初に書いたコードが尾所方ので書き直したが２倍程度しか早くならなかった。
ある部分列があってそれが例えば
1,2,5
1,3
1,7
1,11
で次の数が8なら
1,2,5,8以外は考慮する意味がない。
という視点で計算量を切り落としていけばまあ平凡なタイムを出せます。
#include<stdio.h>
#include<map>
std::map<int,int> memo1;
int memo[100001]={0};
int main(){
int n,a;
std::map<int,int>::iterator it1,it2;
scanf("%d",&n);
scanf("%d",&a);
memo[0]=-1;
memo[1]=a;
n--;
memo1[-1]=0;
memo1[a]=1;
while(n--){
scanf("%d",&a);
it1=it2=memo1.lower_bound(a);
it2--;
if(it1==memo1.end()){
memo[(*it2).second+1]=a;
memo1[a]=(*it2).second+1;
}else{
if((*it2).first<a&&a<(*it1).first){
int num1=(*it1).first;
int count1=(*it1).second;
memo[count1]=a;
memo1[a]=count1;
memo1.erase(num1);
}
}
}
int ans=1;
for(int i=100000;i>=0;i--){
if(memo[i]>0){
ans=i;
break;
}
}
printf("%d\n",ans);
}
*Permutation/Path - Traveling Salesman Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A
巡回セールスマン問題。
解法
この問題とても奥深い研究結果がたくさんあるそうですが私は
とりあえずこの問題が解ければいいやというスタンスでコードを書きました。
１点訪れた集合から２点訪れた集合を
２点訪れた集合から３点訪れた集合を、、、
と続けるだけの単純な動的計画法です。
#include<stdio.h>
#include<map>
struct S{
int nowP,bits;
bool operator<(const S& s)const{
if(nowP!=s.nowP)return nowP<s.nowP;
return bits<s.bits;
}
};
const int NIL=-1;
int G[15][15];
int main(){
std::map<S,int> now,next;
std::map<S,int>::iterator it;
int V,E,s,t,d;
for(int i=0;i<15;i++){
for(int j=0;j<15;j++){
G[i][j]=-1;
}
}
scanf("%d %d",&V,&E);
for(int i=0;i<E;i++){
scanf("%d %d %d",&s,&t,&d);
G[s][t]=d;
}
S s1,s2;
s1.nowP=0;
s1.bits=0;
now[s1]=0;
for(int i=0;i<V;i++){
for(it=now.begin();it!=now.end();it++){
s1=(*it).first;
for(int j=0;j<V;j++){
if(j==0&&i<V-1)continue;
int g=G[s1.nowP][j];
if(g==-1)continue;
int addBit=(1<<j);
if((s1.bits&addBit)>0)continue;
g+=(*it).second;
s2.nowP=j;
s2.bits=(s1.bits|addBit);
if(next.find(s2)==next.end() || next[s2]>g){
next[s2]=g;
}
}
}
now.clear();
now.insert(next.begin(),next.end());
next.clear();
}
it=now.begin();
int ans=-1;
if(it!=now.end())ans=(*it).second;
printf("%d\n",ans);
}
*Combinatorial - Coin Changing Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A
金額を払うのに必要な最小コイン枚数をDPで解く問題。
#include<stdio.h>
#include<vector>
int main(){
int n,m,memo[50001]={0};
scanf("%d %d",&n,&m);
int coin;
for(int i=0;i<m;i++){
scanf("%d",&coin);
for(int j=0;j+coin<=n;j++){
if(memo[j]==0&&j>0)continue;
if(memo[j+coin]==0||memo[j+coin]>memo[j]+1){
memo[j+coin]=memo[j]+1;
}
}
}
printf("%d\n",memo[n]);
}
*Combinatorial - 0-1 Knapsack Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B
重さ付きナップザック問題。
#include<stdio.h>
#include<vector>
int main(){
int n,W,memo[10001]={0};
scanf("%d %d",&n,&W);
int v,w,sum=0,ans=0;
while(n--){
scanf("%d %d",&v,&w);
if(sum+w>W)sum=W-w;
for(int j=sum;j>=0;j--){
if(memo[j+w]<memo[j]+v)memo[j+w]=memo[j]+v;
}
sum+=w;
}
for(int i=0;i<=W;i++)if(ans<memo[i])ans=memo[i];
printf("%d\n",ans);
}
*Combinatorial - Longest Increasing Subsequence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D
数列の中の最長増加部分列の長さをこたえる問題。
最初に書いたコードが低速なので書き直したが２倍程度しか早くならなかった。
これくらいならシンプルな最初のコードのほうが良かったかもしれない。
ある部分列があってそれが例えば
1,2,5
1,3
1,7
1,11
で次の数が8なら
1,2,5,8以外は考慮する意味がない。
という視点で計算量を切り落としていけばまあ平凡なタイムを出せます。
#include<stdio.h>
#include<map>
std::map<int,int> memo1;
int memo[100001]={0};
int main(){
int n,a;
std::map<int,int>::iterator it1,it2;
scanf("%d",&n);
scanf("%d",&a);
memo[0]=-1;
memo[1]=a;
n--;
memo1[-1]=0;
memo1[a]=1;
while(n--){
scanf("%d",&a);
it1=it2=memo1.lower_bound(a);
it2--;
if(it1==memo1.end()){
memo[(*it2).second+1]=a;
memo1[a]=(*it2).second+1;
}else{
if((*it2).first<a&&a<(*it1).first){
int num1=(*it1).first;
int count1=(*it1).second;
memo[count1]=a;
memo1[a]=count1;
memo1.erase(num1);
}
}
}
int ans=1;
for(int i=100000;i>=0;i--){
if(memo[i]>0){
ans=i;
break;
}
}
printf("%d\n",ans);
}
*Permutation/Path - Traveling Salesman Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A
巡回セールスマン問題。
解法
この問題とても奥深い研究結果がたくさんあるそうですが私は
とりあえずこの問題が解ければいいやというスタンスでコードを書きました。
１点訪れた集合から２点訪れた集合を
２点訪れた集合から３点訪れた集合を、、、
と続けるだけの単純な動的計画法です。
#include<stdio.h>
#include<map>
struct S{
int nowP,bits;
bool operator<(const S& s)const{
if(nowP!=s.nowP)return nowP<s.nowP;
return bits<s.bits;
}
};
const int NIL=-1;
int G[15][15];
int main(){
std::map<S,int> now,next;
std::map<S,int>::iterator it;
int V,E,s,t,d;
for(int i=0;i<15;i++){
for(int j=0;j<15;j++){
G[i][j]=-1;
}
}
scanf("%d %d",&V,&E);
for(int i=0;i<E;i++){
scanf("%d %d %d",&s,&t,&d);
G[s][t]=d;
}
S s1,s2;
s1.nowP=0;
s1.bits=0;
now[s1]=0;
for(int i=0;i<V;i++){
for(it=now.begin();it!=now.end();it++){
s1=(*it).first;
for(int j=0;j<V;j++){
if(j==0&&i<V-1)continue;
int g=G[s1.nowP][j];
if(g==-1)continue;
int addBit=(1<<j);
if((s1.bits&addBit)>0)continue;
g+=(*it).second;
s2.nowP=j;
s2.bits=(s1.bits|addBit);
if(next.find(s2)==next.end() || next[s2]>g){
next[s2]=g;
}
}
}
now.clear();
now.insert(next.begin(),next.end());
next.clear();
}
it=now.begin();
int ans=-1;
if(it!=now.end())ans=(*it).second;
printf("%d\n",ans);
}
