Poj 1787 Charie's Change(DP_リュックサック)

テーマリンク:http://poj.org/problem?id=1787
一つの数pを与えて、四種類の貨幣価値を一、5、10、25の硬貨でpにつづり合わせます.そして、硬貨の数が一番多いです.もし解けないなら、「Charie cannot buy coffee.」1<=1万、1<=1万円硬貨の数<=1万円)を出力します.
解題の考え:テーマの第一の考えは多重のリュックサックで、貨幣価値とpを容量と見なして、硬貨の数は価値と見なして、問題は最も容量がpのリュックサックの中で価値が最大でいくらですか?最初はバイナリ処理で多重リュックサックを01バックパックに変えて解いたところ、速度が珍しく969 msで走りました.最適化したら675 msになります.複雑度はO(p*sum(log(num[i])です.ACの後で他の人の解題報告を見て、彼らがすべて完全なリュックサックでこの問題を書いていることを発見しました.複雑なのは(4*p)だけで、スピードは5倍以上速いです.
    二つのバックパックの状態は同じです.dp[j]=max(dp[j],dp[J-mon[i]+val[i])(多重バックパックの解法val[i]==1、<=i==tot,完全バックパックの解法val[i]=1、1<=i=>4)
テストデータ:
12 5 3 1 2 16 0 1 0 1 0 0 0 0 0
コード:

//    
#include <stdio.h>
#include <string.h>
#define MAX 20000


int p,dp[MAX],path[MAX];
int num[50],mon[50],used[MAX];


int main()
{
	int i,j,k,tp;
	mon[1] = 1,mon[2] = 5;
	mon[3] = 10,mon[4] = 25;


	while (scanf("%d",&p)) {

		for (i = 1; i <= 4; ++i)
			scanf("%d",&num[i]);
		if (p == 0) break;
		memset(dp,0,sizeof(dp));
		memset(path,0,sizeof(path));
		path[0] = -1,dp[0] = 1;


		for (i = 1; i <= 4; ++i) {

			memset(used,0,sizeof(used));
			for (j = mon[i]; j <= p; ++j)
				if (dp[j-mon[i]] + 1 > dp[j] && dp[j-mon[i]]
					&& used[j-mon[i]] + 1 <= num[i]) {

					dp[j]   = dp[j-mon[i]] + 1;
					used[j] = used[j-mon[i]] + 1;
					path[j] = j - mon[i];
				}
		}



		if (dp[p] != 0) {
			
			memset(num,0,sizeof(num));
			while (path[p] != -1) {

				num[p-path[p]]++;
				p = path[p];
			}
			printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.
",num[1],num[5],num[10],num[25]);
		}
		else printf("Charlie cannot buy coffee.
");  
	}
	return 0;
}

//    
#include <stdio.h>
#include <string.h>
#define MAX 20000
#define INF 1000000000
#define max(a,b) (a)>(b)?(a):(b)


int num[5],mon[5],in[MAX];
int tot,cost[MAX],val[MAX];
int p,ans,dp[100][MAX],path[100][MAX];


void Solve_1A() {

	int i,j,k;
	tot = 0;
	for (i = 1; i <= 4; ++i) {

		for (j = 0; (1<<j) <= num[i]; ++j) {

			k = 1<<j;
			num[i] -= k;
			cost[++tot] = k * mon[i];
			val[tot]  = k;
			in[tot] = i;
		}
		if (num[i])  {

			in[++tot] = i;
			val[tot]  = num[i];
			cost[tot] = num[i] * mon[i];
		}
		num[i] = 0;				//        ，          
	}


	for (i = 0; i <= tot; ++i)
		for (j = 0; j <= p; ++j)
			path[i][j] = 0,dp[i][j] = -INF;


	dp[0][0] = 0;
	for (i = 1; i <= tot; ++i) {

		for (j = p; j >= 0; --j)
			if (j >= cost[i]) {

				if (dp[i-1][j-cost[i]] != -INF 
					&& dp[i-1][j-cost[i]] + val[i] > dp[i-1][j])
					dp[i][j] = dp[i-1][j-cost[i]] + val[i],path[i][j] = 1;
				else dp[i][j] = dp[i-1][j];
			}
			else dp[i][j] = dp[i-1][j];
	}


	if (dp[tot][p] != -INF) {

		j = tot,k = p;
		while (j > 0) {

			if (path[j][k]) 
				num[in[j]] += val[j],k -= cost[j];
			j--;
		}
	}
}


int main()
{
	int i,j,k;
	mon[1] = 1,mon[2] = 5;
	mon[3] = 10,mon[4] = 25;


	while (scanf("%d",&p)) {

		for (i = 1; i <= 4; ++i)
			scanf("%d",&num[i]);
		if (p == 0) break;


	
		Solve_1A();
		if (dp[tot][p] == -INF)
			printf("Charlie cannot buy coffee.
");
		else 
			printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.
",num[1],num[2],num[3],num[4]);
	}
	return 0;
}

本記事はZero Clockオリジナルですが、兄弟ですので、転載できます.