9.假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量m＝150，设计算法求解怎么装才能使得获取的价值最大？请写出伪代码。

### 回答1：
这是一个假设设计有7个物品的问题，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容积为m=150，则设计算法求解如何装才能得到的价值最大？请写出伪代码。

物品 | 重量 | 价值
---- | ---- | ----
1 | 35 | 10
2 | 30 | 40
3 | 60 | 30
4 | 50 | 50
5 | 40 | 35
6 | 10 | 40
7 | 25 | 30

伪代码：

1. 初始化一个大小为(m+1) x (n+1)的二维数组dp，其中n为物品个数。
2. 将dp数组所有元素的值初始化为0。
3. 对于i从1到n，依次进行以下操作：
- 对于j从1到m，依次进行以下操作：
- 如果第i个物品的重量大于j，则dp[j][i]等于dp[j][i-1]
- 否则，dp[j][i]等于max(dp[j][i-1], dp[j-wi][i-1]+vi)
4. 返回dp[m][n]作为最大价值。

### 回答2：
这是一个典型的01背包问题，可以使用动态规划算法来解决。

首先，我们可以定义一个二维数组dp[i][j]，表示在背包容量为j的情况下，前i个物品能获取的最大价值。其中i的取值范围为1到7，j的取值范围为0到150。

接下来，根据01背包的特点，我们可以得到状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi]+vi)，其中wi和vi分别表示第i个物品的重量和价值。

根据上述方程，我们可以得到如下的伪代码：

//初始化dp数组
for j = 0 to 150 do
dp[0][j] = 0
end
//填充dp数组
for i = 1 to 7 do
for j = 0 t0 150 do
if j < wi then
dp[i][j] = dp[i-1][j]
else
dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi]+vi)
end
end
end
//输出最大价值
print(dp[7][150])

最后的输出结果即为问题的解，即为获取的最大价值。

### 回答3：
这道题可以使用动态规划来解决。假设f[i][j]表示前i个物品装进容量为j的背包中所能获得的最大价值。则可以得到以下状态转移方程：

f[i][j] = max{ f[i-1][j], f[i-1][j-w[i]] + v[i] } （j >= w[i]）

f[i][j] = f[i-1][j] （j < w[i]）

其中w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。

然后，初始化f数组的第0行和第0列为0，因为不装物品或背包容量为0时获得的价值均为0。

最后，返回f[7][150]，即可得到最大价值。

伪代码如下：

for i = 1 to 7
for j = 1 to 150
if j < w[i] then
f[i][j] = f[i-1][j]
else
f[i][j] = max{ f[i-1][j], f[i-1][j-w[i]] + v[i] }
end if
end for
end for

return f[7][150]