質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.48%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

2回答

969閲覧

C言語で動的計画法(ナップサック問題)を用いて最大出勤日を出す

wanwanko

総合スコア14

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2022/04/25 14:32

動的計画法を用いて、仕事開始日と終了日を入力して、どの連勤を選べば出勤日が最大になるかについて書いてみました。
参考にした問題が以下です。

現在、サスケは複数のクライアントから依頼を受け取っており、各依頼にはクライアントが指定した開始日と完了日があります(必要な稼働日数は完了日から開始日を引いたものです)サスケはどの注文を約束するかを知りませんでした。

複数のクライアントによって指定された開始日と完了日、およびサスケの作業の開始日と終了日を知っているので、サスケが最大の収入を得ることができるように、サスケがクライアントの依頼を選択するのを手伝ってください。

たとえば、サスケは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日間の収入です。

C

1コード 2#include <stdio.h> 3 4int max(int a, int b) 5{ return (a > b) ? a : b; } 6 7int knapSack(int W, int *wt, int *val, int n) 8{ 9 if (n == 0 || W == 0) 10 return 0; 11 12 if (wt[n - 1] > W) 13 return knapSack(W, wt, val, n - 1); 14 15 else 16 return max( 17 val[n - 1] 18 + knapSack(W - wt[n - 1], 19 wt, val, n - 1), 20 knapSack(W, wt, val, n - 1)); 21} 22 23int main() 24{ int item; 25 scanf("%d",&item); 26 int val[item],wt[item]; 27 for(int i=0;i<item;++i) 28 scanf("%d%d",&val[i],&wt[i]); 29 30 int start,end; 31 scanf("%d%d",&start,&end); 32 33 printf("%d\n",knapSack(end, wt, val, item)); 34 return 0; 35}

このように書いてみたのですが、7つのクライアントの依頼日を入力した時には13 と出力されます。
何回も繰り返しコードを見直し書き直したのですが、どうしても最大の14日間にはならないので質問させていただきました。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

jimbe

2022/04/26 10:15

> 7つのクライアントの依頼日を入力した時には13 と出力 > どうしても最大の14日間にはならない どの依頼を受けることになって 13 になっているのか、そして、14 になる場合と 13 になる場合では受けるどの依頼が違うのか、さらに、その依頼の違いは何によっておきているのか…等はお調べになったのでしょうか。
guest

回答2

0

まずは、こちらのページ「動的計画法超入門! Educational DP Contest の A ~ E 問題の解説と類題集」を読んでください。
以下の解説は、「実際に手を動かして DP を体験してみる」まで読んでいることを前提としています。

まず、サスケが1日目にとれる行動の選択肢は、以下の2つになります。

  1. 1日目は休む(出勤日は変わらず)
  2. 開始日が1日目の依頼をこなす(出勤日が5日増える)

休むことを選んだ場合は、次の日(2日目)に改めて行動を選択します。
依頼をこなす場合は、依頼の完了日(6日目)に改めて行動を選択することになります。

同様に、2日目は休むしか選択肢が無く、3日目は休むか7日目まで依頼をこなすかのどちらかになります。

このように日付をたどっていくと考えると、カエルの問題と同様の構造になっていることが分かります。
カエルの問題は移動先が1つ隣、2つ隣の2択でしたが、この問題は移動先が次の日 or 依頼完了日となる、というだけです。

そのため、こちらの問題についても、カエルの問題と同様に、開始日をスタート、終了日をゴールとしたグラフを書けるはずです。
あとは、同様にDP値を先頭から埋めていけば、こちらの問題を解くことが可能です。

投稿2023/04/07 16:16

actorbug

総合スコア2224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

val の値と start の値を全く使っていませんね。
wt の値と end の値だけで正しい結果が得られるとは思えません。

追記
書いてみました。

c

1#include <stdio.h> // scanf, printf 2#include <string.h> // memset, memchr 3 4int max(int a, int b) { return a > b ? a : b; } 5 6int knapsack(int w, int a[], int b[], int n, char t[]) 7{ 8 if (--n < 0) return w; 9 int len = b[n] - a[n]; 10 if (memchr(t + a[n], 1, len)) return knapsack(w, a, b, n, t); 11 memset(t + a[n], 1, len); 12 int k = knapsack(w + len, a, b, n, t); 13 memset(t + a[n], 0, len); 14 return max(k, knapsack(w, a, b, n, t)); 15} 16 17int main(void) 18{ 19 int n, m = 0, start, end; 20 scanf("%d", &n); 21 int a[n], b[n]; 22 for (int i = 0; i < n; i++) { 23 scanf("%d%d", &a[i], &b[i]); 24 if (b[i] > m) m = b[i]; 25 } 26 scanf("%d%d", &start, &end); 27 if (end > m) m = end; 28 char t[m]; 29 memset(t, 1, m); 30 memset(t + start, 0, end - start); 31 printf("%d\n", knapsack(0, a, b, n, t)); 32}

投稿2022/04/25 15:53

編集2022/04/27 14:22
kazuma-s

総合スコア8224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.48%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問