题目描述

题目：多维动态规划 - 背包问题扩展

在经典的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));

这些示例代码都使用了四维动态规划数组来存储中间结果，并通过迭代每个物品和每种资源限制的组合来找到最优解。