租用游艇问题动态规划c语言

租用游艇问题是一个经典的动态规划问题，可以用C语言进行解决。

问题描述：假设你在一个海滩上，有一些人想要租用你的小船。你可以选择将船租给这些人中的任意一个，每个人租用船的时间和价格都不同。你需要在有限的时间内，最大化你的收益。

解决方案：我们可以使用动态规划来解决这个问题。我们可以定义一个二维数组dp[i][j]，其中i表示当前时间，j表示当前可租用的人数。dp[i][j]表示在当前时间和可租用人数下，最大化的收益。

我们可以通过以下公式来更新dp数组：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+p[i])

其中p[i]表示第i个人租用小船的价格，dp[i-1][j]表示不租给第i个人的收益，dp[i-1][j-1]+p[i]表示租给第i个人的收益。

最后的答案就是dp[T][N]，其中T为总时间，N为总可租用的人数。

下面是C语言代码实现：

#include <stdio.h>

#define MAX_N 100
#define MAX_T 1000

int dp[MAX_T+1][MAX_N+1];
int p[MAX_N+1];
int t, n;

int main() {
    scanf("%d %d", &t, &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
    }

    for (int i = 1; i <= t; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i-1][j];
            if (i >= p[j]) {
                dp[i][j] = max(dp[i][j], dp[i-p[j]][j-1]+p[j]);
            }
        }
    }

    printf("%d\n", dp[t][n]);
    return 0;
}