船费问题动态规划java

本题可以使用动态规划来解决。首先，我们可以考虑定义状态。设$f[i][j]$表示到第i个城市，并且船费用不超过j元的最小花费。那么最终的答案即为$f[N][K]$，其中N表示城市数量，K表示船费的上限。接下来我们考虑状态转移方程。

对于第i个城市，我们可以选择不乘坐船或者选择乘坐某一艘船。如果我们不乘坐船，那么$f[i][j]$就等于$f[i-1][j]$；如果我们选择乘坐某一艘船，那么$f[i][j]$就等于$f[i-1][j-cost[i][k]]+fee[i][k]$，其中cost[i][k]表示从第i-1个城市到第i个城市乘坐第k艘船的花费，fee[i][k]表示在第i个城市乘坐第k艘船的花费。因此，状态转移方程为：

$f[i][j]=\min(f[i-1][j],f[i-1][j-cost[i][k]]+fee[i][k])$

最后，我们可以使用一维数组来优化空间，因为在状态转移过程中只需要用到f[i-1]的值，因此我们可以将二维数组压缩成一维数组。具体实现细节请见下方的Java代码。

Java代码：

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); //城市数量
        int m = in.nextInt(); //船的数量
        int k = in.nextInt(); //船费的上限
        int[][] cost = new int[n + 1][m + 1]; //从第i-1个城市到第i个城市乘坐第j艘船的花费
        int[][] fee = new int[n + 1][m + 1]; //在第i个城市乘坐第j艘船的花费
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cost[i][j] = in.nextInt();
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                fee[i][j] = in.nextInt();
            }
        }
        int[] f = new int[k + 1]; //一维数组
        Arrays.fill(f, Integer.MAX_VALUE / 2); //初始化为最大值的一半
        f[0] = 0; //初始状态
        for (int i = 1; i <= n; i++) {
            for (int j = k; j >= 0; j--) {
                for (int p = 1; p <= m; p++) {
                    if (j >= cost[i][p]) {
                        f[j] = Math.min(f[j], f[j - cost[i][p]] + fee[i][p]);
                    }
                }
            }
        }
        System.out.println(f[k]); //输出答案
    }
}