整数分区加权最小值
Integer partition weighted minimum
给定一个非负整数 $n$ 和一个维度为 $m$ 的正实数权重向量 $w$，将 $n$ 划分为一个总和为 $n 的长度为 $m$ 的非负整数向量$（称之为 $v$）使得 $w\cdot v$ 是最小的。可能有多个分区，我们只想要 $w\cdot v$.
的值
看来这道题可以用贪心算法来解决。从 $n-1$ 的目标向量中，我们将每个条目加 1，然后找到这 $m$ 个向量中的最小值。但我不认为这是正确的。直觉是它可能会“超过”最小值。也就是说，存在另一个分区不是由 add 1 过程产生的，它落在这个贪婪算法产生的 $n-1$ 的“最小值”和这个贪婪算法产生的 $n$ 的“最小值”之间。谁能证明这是对还是错？
不失一般性，假设w的元素是non-decreasing。设 v 为 m 向量，其值为 non-negative 个整数，总和为 n。那么v和w的最小内积是通过设置v[0] = n和v[i] = 0为i > 0.
来实现的
这很容易证明。假设 v 是 v[i] > 0 对于某些 i > 0 的任何其他向量。然后我们可以将 v[0] 增加 v[i] 并将 v[i] 减少为零。 v 的元素总和仍为 n，v 和 w 的内积将减少 w[i] - w[0] >= 0。
给定一个非负整数 $n$ 和一个维度为 $m$ 的正实数权重向量 $w$，将 $n$ 划分为一个总和为 $n 的长度为 $m$ 的非负整数向量$（称之为 $v$）使得 $w\cdot v$ 是最小的。可能有多个分区，我们只想要 $w\cdot v$.
的值看来这道题可以用贪心算法来解决。从 $n-1$ 的目标向量中，我们将每个条目加 1，然后找到这 $m$ 个向量中的最小值。但我不认为这是正确的。直觉是它可能会“超过”最小值。也就是说，存在另一个分区不是由 add 1 过程产生的，它落在这个贪婪算法产生的 $n-1$ 的“最小值”和这个贪婪算法产生的 $n$ 的“最小值”之间。谁能证明这是对还是错？
不失一般性，假设w的元素是non-decreasing。设 v 为 m 向量，其值为 non-negative 个整数，总和为 n。那么v和w的最小内积是通过设置v[0] = n和v[i] = 0为i > 0.
这很容易证明。假设 v 是 v[i] > 0 对于某些 i > 0 的任何其他向量。然后我们可以将 v[0] 增加 v[i] 并将 v[i] 减少为零。 v 的元素总和仍为 n，v 和 w 的内积将减少 w[i] - w[0] >= 0。