当前位置： 面试刷题>> 多维动态规划(经典算法150题)
### 题目描述
**题目：多维动态规划 - 背包问题扩展**
在经典的0-1背包问题基础上，我们将其扩展到多维情况。假设你有一个背包，它可以承受的最大重量为`W`，并且除了重量限制外，还有另外两种资源限制：体积`V`和温度承受能力`T`。现在，你面前有`N`个物品，每个物品`i`具有重量`wt[i]`、体积`vol[i]`、温度承受能力`temp[i]`和价值`val[i]`。你的目标是选择一些物品放入背包中，使得这些物品的总价值最大，同时不超过背包的任何一项资源限制（重量、体积、温度承受能力）。
**输入**：
- `N`：物品数量
- `W`：背包最大重量
- `V`：背包最大体积
- `T`：背包最大温度承受能力
- `wt[]`：物品重量数组
- `vol[]`：物品体积数组
- `temp[]`：物品温度承受能力数组
- `val[]`：物品价值数组
**输出**：
- 能够放入背包的物品的最大总价值
### 示例代码
以下是使用PHP、Python和JavaScript编写的解决该问题的示例代码。
#### PHP 示例
```php
function maxValueInKnapsack($N, $W, $V, $T, $wt, $vol, $temp, $val) {
$dp = array_fill(0, $N+1, array_fill(0, $W+1, array_fill(0, $V+1, array_fill(0, $T+1, 0))));
for ($i = 1; $i <= $N; $i++) {
for ($w = 0; $w <= $W; $w++) {
for ($v = 0; $v <= $V; $v++) {
for ($t = 0; $t <= $T; $t++) {
if ($wt[$i-1] <= $w && $vol[$i-1] <= $v && $temp[$i-1] <= $t) {
$dp[$i][$w][$v][$t] = max(
$dp[$i-1][$w][$v][$t], // 不选择当前物品
$dp[$i-1][$w-$wt[$i-1]][$v-$vol[$i-1]][$t-$temp[$i-1]] + $val[$i-1] // 选择当前物品
);
} else {
$dp[$i][$w][$v][$t] = $dp[$i-1][$w][$v][$t]; // 不选择当前物品
}
}
}
}
}
return $dp[$N][$W][$V][$T];
}
// 示例输入
$N = 3;
$W = 50;
$V = 100;
$T = 20;
$wt = [10, 20, 30];
$vol = [20, 40, 60];
$temp = [5, 10, 15];
$val = [60, 100, 120];
// 调用函数并输出结果
echo maxValueInKnapsack($N, $W, $V, $T, $wt, $vol, $temp, $val);
```
#### Python 示例
```python
def maxValueInKnapsack(N, W, V, T, wt, vol, temp, val):
dp = [[[[0 for _ in range(T+1)] for _ in range(V+1)] for _ in range(W+1)] for _ in range(N+1)]
for i in range(1, N+1):
for w in range(W+1):
for v in range(V+1):
for t in range(T+1):
if wt[i-1] <= w and vol[i-1] <= v and temp[i-1] <= t:
dp[i][w][v][t] = max(dp[i-1][w][v][t], dp[i-1][w-wt[i-1]][v-vol[i-1]][t-temp[i-1]] + val[i-1])
else:
dp[i][w][v][t] = dp[i-1][w][v][t]
return dp[N][W][V][T]
# 示例输入
N, W, V, T = 3, 50, 100, 20
wt, vol, temp, val = [10, 20, 30], [20, 40, 60], [5, 10, 15], [60, 100, 120]
# 调用函数并输出结果
print(maxValueInKnapsack(N, W, V, T, wt, vol, temp, val))
```
#### JavaScript 示例
```javascript
function maxValueInKnapsack(N, W, V, T, wt, vol, temp, val) {
const dp = new Array(N+1).fill(0).map(() =>
new Array(W+1).fill(0).map(() =>
new Array(V+1).fill(0).map(() =>
new Array(T+1).fill(0)
)
)
);
for (let i = 1; i <= N; i++) {
for (let w = 0; w <= W; w++) {
for (let v = 0; v <= V; v++) {
for (let t = 0; t <= T; t++) {
if (wt[i-1] <= w && vol[i-1] <= v && temp[i-1] <= t) {
dp[i][w][v][t] = Math.max(dp[i-1][w][v][t], dp[i-1][w-wt[i-1]][v-vol[i-1]][t-temp[i-1]] + val[i-1]);
} else {
dp[i][w][v][t] = dp[i-1][w][v][t];
}
}
}
}
}
return dp[N][W][V][T];
}
// 示例输入
const N = 3, W = 50, V = 100, T = 20;
const wt = [10, 20, 30], vol = [20, 40, 60], temp = [5, 10, 15], val = [60, 100, 120];
// 调用函数并输出结果
console.log(maxValueInKnapsack(N, W, V, T, wt, vol, temp, val));
```
这些示例代码都使用了四维动态规划数组来存储中间结果，并通过迭代每个物品和每种资源限制的组合来找到最优解。