【动态规划】小S的货船租赁冒险

一、问题描述

李华在码头租货船，有 Q 种货船可以租赁。第 i 种货船的数量为 m[i], 租赁价格为 v[i]，载货量为 w[i]。求预算为 V 的情况下，李华租的货船载货量总和 W 最大为多少？

输入格式

共两行。

第 1 行为两个用空格分隔开的整数：Q(1 <= Q <= 50) 、V(1 <= V <= 4000) 。Q 表示货船种类数，V 表示李华的预算。

第 2 行到第 Q + 1 行是 Q 种货船的详细信息。第 i + 1(1 <= i <= Q) 行有三个用空格分隔开的整数：m[i](1 <= m[i] <= 1000) 、v[i](1 <= v[i] <= 100) 、w[i](1 <= w[i] <= 100) ，表示第 i 种货船的数量、租赁价格和载货量。

输出格式

输出李华预算为 V 的情况下，货船载货量总和 W 的最大值。

问题背景

李华想通过预算限制，在码头租用货船以最大化货物载量。每种货船有数量限制、租赁成本和载货量。目的是找到一种最优租船方案，使总预算不超过 ( V )，并让货物载量达到最大。这是典型的多重背包问题。

二、动态规划思想

动态规划的核心是将问题分解为子问题，利用子问题的最优解构建原问题的最优解。具体到本问题，可以通过如下步骤构造解法：

1. 状态定义：
   定义 dp[i][j] 表示前 ( i ) 种货船在预算为 ( j ) 时的最大载货量。

   • ( i ) 代表当前考虑到的货船种类数。
   • ( j ) 代表当前可用的预算。

2. 状态转移：

   • 不选择当前第 ( i ) 种货船时，最大载货量为前 ( i-1 ) 种货船在预算为 ( j ) 时的最大载货量，即 dp[i][j] = dp[i-1][j]。

   • 如果选择第 ( i ) 种货船，则需要从预算 ( j ) 中扣除相应的租赁成本，同时增加载货量。可以选择 ( k ) 艘船,
     

   • 遍历 ( k ) 直到预算或货船数量的限制。

3. 边界条件：

   • 当没有货船或预算为 0 时，最大载货量为 0，即 dp[0][j] = 0 和 dp[i][0] = 0。

4. 结果输出：

   • 最终答案为 dp[Q][V]，表示考虑所有 ( Q ) 种货船并且预算为 ( V ) 时的最大载货量。

三、代码实现细节

初始化二维数组

二维数组 dp 用于存储中间状态结果，其大小为 (Q+1)* (V+1) 。所有初始值均为 0，表示当预算不足或没有船可用时，最大载货量为 0。

int[][] dp = new int[Q + 1][V + 1];

遍历每种货船

外层循环遍历所有货船。对于每种货船，获取其数量 ( m )、租赁成本 ( v ) 和载货量 ( w )。

for (int i = 1; i <= Q; i++) {int m = ships.get(i - 1).get(0); // 数量int v = ships.get(i - 1).get(1); // 成本int w = ships.get(i - 1).get(2); // 载货量

遍历预算并更新状态

对于当前货船 ( i )，内层循环遍历预算 ( j ) 从 ( 0 ) 到 ( V )，计算每种选择下的最优解。

• 不选择当前货船：

  dp[i][j] = dp[i - 1][j];
  

• 遍历选择 1 到 ( m ) 艘货船：

  for (int k = 1; k <= m; k++) {if (j >= k * v) {dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * v] + k * w);} else {break; // 提前退出循环}
  }
  

提前剪枝优化

当预算 ( j ) 不足以选择 ( k ) 艘船时，直接退出循环，避免无效计算。

四、代码实现

import java.util.ArrayList;
import java.util.List;public class Main {public static int solution(int Q, int V, List<List<Integer>> ships) {// 初始化二维数组 dp，大小为 (Q + 1) x (V + 1)int[][] dp = new int[Q + 1][V + 1];// 遍历每种货船for (int i = 1; i <= Q; i++) {int m = ships.get(i - 1).get(0); // 当前货船的数量int v = ships.get(i - 1).get(1); // 当前货船的租赁成本int w = ships.get(i - 1).get(2); // 当前货船的载货量// 遍历预算，从 0 到 Vfor (int j = 0; j <= V; j++) {// 不选择第 i 种货船dp[i][j] = dp[i - 1][j];// 遍历选择 k 艘当前货船for (int k = 1; k <= m; k++) {if (j >= k * v) {dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * v] + k * w);} else {break; // 如果预算不足，提前退出循环}}}}// 返回在预算 V 内的最大载货量return dp[Q][V];}public static void main(String[] args) {// 测试用例List<List<Integer>> ships = new ArrayList<>();ships.add(List.of(2, 3, 2));ships.add(List.of(3, 2, 10));List<List<Integer>> ships2 = new ArrayList<>();ships2.add(List.of(30, 141, 47));ships2.add(List.of(9, 258, 12));ships2.add(List.of(81, 149, 13));ships2.add(List.of(91, 236, 6));ships2.add(List.of(27, 163, 74));ships2.add(List.of(34, 13, 58));ships2.add(List.of(61, 162, 1));ships2.add(List.of(80, 238, 29));ships2.add(List.of(36, 264, 28));ships2.add(List.of(36, 250, 2));ships2.add(List.of(70, 214, 31));ships2.add(List.of(39, 116, 39));ships2.add(List.of(83, 287, 4));ships2.add(List.of(61, 269, 94));ships2.add(List.of(23, 187, 46));ships2.add(List.of(78, 33, 29));ships2.add(List.of(46, 151, 2));ships2.add(List.of(71, 249, 1));ships2.add(List.of(67, 76, 85));ships2.add(List.of(72, 239, 17));ships2.add(List.of(61, 256, 49));ships2.add(List.of(48, 216, 73));ships2.add(List.of(39, 49, 74));System.out.println(solution(2, 10, ships) == 32);System.out.println(solution(23, 400, ships2) == 1740);}
}

算法复杂度分析

1. 时间复杂度：

   • 外层循环遍历 Q 种货船。
   • 每种货船最多需要遍历预算 ( V )，并对 ( m[i] ) 的数量进行内部循环。
   • 总时间复杂度为 ( O(Q * V * m )，其中 ( m ) 为每种货船的平均数量。

2. 空间复杂度：

   • 使用二维数组 dp，空间复杂度为 O(Q * V) 。

优化思路

1. 空间优化：

   • 使用一维数组滚动优化，将 dp[i][j] 转换为 dp[j]，仅保留上一层的状态，减少空间复杂度到 ( O(V) )。

2. 二进制拆分优化：

   • 使用二进制拆分将多重背包问题转化为若干个 0-1 背包问题，减少内部循环次数。

间复杂度为 O(Q * V) 。

博客主页: 总是学不会.