题目描述
题目:多维动态规划 - 背包问题扩展
在经典的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 示例
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 示例
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 示例
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));
这些示例代码都使用了四维动态规划数组来存储中间结果,并通过迭代每个物品和每种资源限制的组合来找到最优解。