Sam的背包问题 - 题解 - Sanhai

1
sanhai V LV 5 SU @ 2026-9-12 21:38:11
题解

设选中物品的总重量为 $h$ ，总体积为 $(v$ 。

神奇背包需要存在一个自然数 $x$ ，满足：
$h\le H-x,\quad v\le V+x$
化简：
$x\le H-h$ $x\ge v-V$
又因为 $x\ge0$ ，所以：
$\max(0,v-V)\le H-h$
等价于：
$\boxed{h\le H,\quad h+v\le H+V}$
因此问题变成：

选择若干物品，使：
- 总重量不超过 (H)
- 总重量 + 总体积不超过 (H+V)
价值最大。

DP

定义：
$dp[i][j]$
表示当前总重量为 (i)，总体积为 (j) 时的最大价值。

转移：
$dp[i][j]=\max(dp[i][j],dp[i-h][j-v]+w)$
因为物品只能选一次，所以两个维度倒序枚举。

初始化：
```
dp[0][0]=0
```
其余为负无穷

最后枚举所有：
$i\le H,\ i+j\le H+V$
取最大值。

复杂度

状态数：
$O(H(H+V))$
转移：
$O(nH(H+V))$

View all 6 solutions

ID: 2736
时间: 1000ms
内存: 64MiB
难度: 3
标签: (无)
递交数: 53
已通过: 13
上传者: Sam