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

Question

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

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

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

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

コード
#include <stdio.h>
  
int max(int a, int b) 
{ return (a > b) ? a : b; }
  
int knapSack(int W, int *wt, int *val, int n)
{
    if (n == 0 || W == 0)
        return 0;
  
    if (wt[n - 1] > W)
        return knapSack(W, wt, val, n - 1);
  
    else
        return max(
            val[n - 1]
                + knapSack(W - wt[n - 1], 
                           wt, val, n - 1),
            knapSack(W, wt, val, n - 1));
}

int main()
{   int item;
    scanf("%d",&item);
    int val[item],wt[item];
    for(int i=0;i<item;++i)
        scanf("%d%d",&val[i],&wt[i]);
    
 	int start,end;
    scanf("%d%d",&start,&end);

    printf("%d\n",knapSack(end, wt, val, item));
    return 0;
}

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

Comments

[jimbe]

> ７つのクライアントの依頼日を入力した時には13 と出力
> どうしても最大の14日間にはならない

どの依頼を受けることになって 13 になっているのか、そして、14 になる場合と 13 になる場合では受けるどの依頼が違うのか、さらに、その依頼の違いは何によっておきているのか…等はお調べになったのでしょうか。

Answer 1

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

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

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

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

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

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

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

Answer 2

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

追記
書いてみました。

#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 n, m = 0, start, end;
	scanf("%d", &n);
	int a[n], b[n];
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &a[i], &b[i]);
		if (b[i] > m) m = b[i];
	}
	scanf("%d%d", &start, &end);
	if (end > m) m = end;
	char t[m];
	memset(t, 1, m);
	memset(t + start, 0, end - start);
	printf("%d\n", knapsack(0, a, b, n, t));
}