Combinatorial - Coin Changing Problem
#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
#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
#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);
}
最終更新:2014年01月28日 08:39