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

「AOJ Problem Set from DPL 問0~4」の編集履歴(バックアップ)一覧に戻る

AOJ Problem Set from DPL 問0~4 - (2014/01/28 (火) 03:54:51) の編集履歴(バックアップ)


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