现有一个集装箱限重 1000。有 100 种物品每种物品的重量wi为正整数且wi是1到50之间的随机数；价值vi为正整数且vi是10到100之间的随机数。利用动态规划算法求解不超重情况下装入物品价值最大的最优装配方案。并分析实验结果。先生成 100 种物品的重量和价值再进行计算

首先，我们可以将问题转化为一个经典的背包问题。将每种物品看作一个物品，将其重量作为物品的重量，将其价值作为物品的价值。然后，我们可以使用动态规划算法求解最优解。具体步骤如下：

1. 定义状态：设 dp[i][j] 表示将前 i 个物品装进限重为 j 的背包中所能获得的最大价值。

2. 状态转移方程：对于第 i 个物品，我们有两种决策：装入或不装入背包。如果不装入背包，则 dp[i][j] = dp[i-1][j]；如果装入背包，则 dp[i][j] = dp[i-1][j-wi] + vi。因此，状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)

3. 边界条件：当 i=0 或 j=0 时，dp[i][j] = 0。

4. 最终结果：dp[100][1000] 即为所求。

代码实现如下：

import random

weight = [random.randint(1, 50) for i in range(100)] # 生成100种物品的重量 value = [random.randint(10, 100) for i in range(100)] # 生成100种物品的价值

max_weight = 1000 # 背包的限重 dp = [[0 for j in range(max_weight+1)] for i in range(101)] # 初始化dp数组

for i in range(1, 101): for j in range(1, max_weight+1): if j >= weight[i-1]: dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]] + value[i-1]) else: dp[i][j] = dp[i-1][j]

print(dp[100][1000]) # 输出最大价值

实验结果表明，对于这个问题，动态规划算法可以在较短的时间内求解最优解。对于这个具体问题，最大价值为 2456