※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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


#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
数列の中の最長増加部分列の長さをこたえる問題。
最初に書いたコードが低速なので書き直したが2倍程度しか早くならなかった。
これくらいならシンプルな最初のコードのほうが良かったかもしれない。
ある部分列があってそれが例えば
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
巡回セールスマン問題。
解法
この問題とても奥深い研究結果がたくさんあるそうですが私は
とりあえずこの問題が解ければいいやというスタンスでコードを書きました。
1点訪れた集合から2点訪れた集合を
2点訪れた集合から3点訪れた集合を、、、
と続けるだけの単純な動的計画法です。



#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);
}