魔兽争霸3多重背包问题动态规划解法与代码实现

　　动态规划解决魔兽争霸3多重背包问题

　　结构体定义

　　`struct node` 定义了一个包含物品体积 `v` 和重量 `w` 的结构体。

　　Max函数

　　`Max` 函数用于返回两个整数中的较大值。

　　主函数

　　`main` 函数是程序的入口点。它首先读取测试用例数量 `nCase` 和背包容量 `nVal`，然后读取每个物品的体积和重量，并存储在数组 `g` 中。接下来，初始化动态规划数组 `dp`，并使用嵌套循环遍历所有物品和所有可能的背包容量，更新 `dp` 数组以记录最大权值。最后，输出 `dp[nVal]`，即背包容量为 `nVal` 时的最大权值。

　　动态规划解法详解

　　状态定义

　　`f[i][v]` 表示前 `i` 种物品恰放入一个容量为 `v` 的背包的最大权值。

　　状态转移方程

　　`f[i][v] = max{ f[i][v], f[i-1][v k*w[i]] + k*c[i] }`，其中 `0
<= k <= n[i]`。

　　初始化

　　`dp = 0`，因为容量为 `0` 时没有物品可以放入。

　　结果

　　最终结果存储在 `dp[nVal]` 中。

　　时间复杂度

　　这个算法的时间复杂度是 `O(V * sum(n[i]))`，其中 `V` 是背包容量，`n[i]` 是第 `i` 种物品的数量。