とあるonline judgeの問題を書きました。時間計算量が大きいためtime exceedと表示されます。時間計算量を削減するため、メモ化にしたいのです。
以下は、再帰で実装したcodeで、メモ化したいcodeです。
[code]#include <stdio.h> // scanf, printf
#include <string.h> // memset, memchr
int max(int a, int b) { return a > b ? a : b; }
int knapsack(int w, int a[], int b[], int n, char t[])
{
if (--n < 0) return w;
int len = b[n] - a[n];
if (memchr(t + a[n], 1, len)) return knapsack(w, a, b, n, t);
memset(t + a[n], 1, len);
int k = knapsack(w + len, a, b, n, t);
memset(t + a[n], 0, len);
return max(k, knapsack(w, a, b, n, t));
}
int main(void)
{
int number_of_client, max = 0, start, end;
scanf("%d", &number_of_client);
int jobs_start[number_of_client], jobs_end[number_of_client];
for (int i = 0; i < number_of_client; i++) {
scanf("%d%d", &jobs_start[i], &jobs_end[i]);
if (jobs_end[i] > max) max = jobs_end[i];
}
scanf("%d%d", &start, &end);
if (end > max) max = end;
char t[max];
memset(t, 1, max);//tを初期化
memset(t + start, 0, end - start);
printf("%d\n", knapsack(0, jobs_start, jobs_end, number_of_client, t));
}
[/code]
Description:
現在、サスケは複数のクライアントから依頼を受け取っており、各依頼にはクライアントが指定した開始日と完了日があります(必要な稼働日数は完了日から開始日を引いたものです)サスケはどの注文を約束するかを知りませんでした。
複数のクライアントによって指定された開始日と完了日、およびサスケの作業の開始日と終了日を知っているので、サスケが最大の収入を得ることができるように、サスケがクライアントの依頼を選択するのを手伝ってください。
たとえば、サスケは7つのクライアントの依頼を受け取り、指定された日付と完了日は{[6、10]、[10,12]、[8,13]、[3,7]、[1,6]、[13 、16]、[5、9]}、サスケが{[1,6]、[6,10]、[10,12]、[13,16]を選択した場合、サスケは1日目から16日目まで動作することが知られています。 ]}これら4人の顧客の手数料であるサスケの収入が最も多く、合計で5 + 4 + 2 + 3=14日間の収入があります。マリオが3日目から12日目まで働く場合は、{[3,7]、[10,12]}または{[5、9]、[10、12]}または{[6、10]、[10、12 ]}手数料、マリオが最も収入があり、合計4 + 2=6日間の収入です。
sample input
7
6 10
10 12
8 13
3 7
1 6
13 16
5 9
1 16
sample output
14
C言語のコードを再帰からメモ化にしたい
Re: C言語のコードを再帰からメモ化にしたい
ソースコードを提示する際は、BBCodeが有効な(無効にしない)状態で、
BBCodeのcodeタグの開始タグと終了タグの組(開始タグが先)で囲んでいただけると、
見やすくてありがたいです。
C言語で動的計画法(ナップサック問題)を用いて最大出勤日を出す
(約1年前の質問で、コードも違うので、マルチポストではないでしょう)
質問はありますか?
BBCodeのcodeタグの開始タグと終了タグの組(開始タグが先)で囲んでいただけると、
見やすくてありがたいです。
制約が知りたいですが、問題文の一部でググってもここしか出なそうでわかりませんね…
C言語で動的計画法(ナップサック問題)を用いて最大出勤日を出す
(約1年前の質問で、コードも違うので、マルチポストではないでしょう)
すればいいのではないでしょうか?
質問はありますか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: C言語のコードを再帰からメモ化にしたい
[/nfo]
ワニ さんが書きました: ↑1年前とあるonline judgeの問題を書きました。時間計算量が大きいためtime exceedと表示されます。時間計算量を削減するため、メモ化にしたいのです。
以下は、再帰で実装したcodeで、メモ化したいcodeです。
Description:#include <stdio.h> // scanf, printf #include <string.h> // memset, memchr int max(int a, int b) { return a > b ? a : b; } int knapsack(int w, int a[], int b[], int n, char t[]) { if (--n < 0) return w; int len = b[n] - a[n]; if (memchr(t + a[n], 1, len)) return knapsack(w, a, b, n, t); memset(t + a[n], 1, len); int k = knapsack(w + len, a, b, n, t); memset(t + a[n], 0, len); return max(k, knapsack(w, a, b, n, t)); } int main(void) { int number_of_client, max = 0, start, end; scanf("%d", &number_of_client); int jobs_start[number_of_client], jobs_end[number_of_client]; for (int i = 0; i < number_of_client; i++) { scanf("%d%d", &jobs_start[i], &jobs_end[i]); if (jobs_end[i] > max) max = jobs_end[i]; } scanf("%d%d", &start, &end); if (end > max) max = end; char t[max]; memset(t, 1, max);//tを初期化 memset(t + start, 0, end - start); printf("%d\n", knapsack(0, jobs_start, jobs_end, number_of_client, t)); }
現在、サスケは複数のクライアントから依頼を受け取っており、各依頼にはクライアントが指定した開始日と完了日があります(必要な稼働日数は完了日から開始日を引いたものです)サスケはどの注文を約束するかを知りませんでした。
複数のクライアントによって指定された開始日と完了日、およびサスケの作業の開始日と終了日を知っているので、サスケが最大の収入を得ることができるように、サスケがクライアントの依頼を選択するのを手伝ってください。
たとえば、サスケは7つのクライアントの依頼を受け取り、指定された日付と完了日は{[6、10]、[10,12]、[8,13]、[3,7]、[1,6]、[13 、16]、[5、9]}、サスケが{[1,6]、[6,10]、[10,12]、[13,16]を選択した場合、サスケは1日目から16日目まで動作することが知られています。 ]}これら4人の顧客の手数料であるサスケの収入が最も多く、合計で5 + 4 + 2 + 3=14日間の収入があります。マリオが3日目から12日目まで働く場合は、{[3,7]、[10,12]}または{[5、9]、[10、12]}または{[6、10]、[10、12 ]}手数料、マリオが最も収入があり、合計4 + 2=6日間の収入です。
sample input
7
6 10
10 12
8 13
3 7
1 6
13 16
5 9
1 16
sample output
14