You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

带概率分布L1偏差约束的有界背包最大化问题LP松弛的求解策略问询

带概率分布L1偏差约束的有界背包最大化问题LP松弛的求解策略问询

我现在遇到了一个和经典有界背包LP松弛问题很相似的优化问题,想请教下大家的求解思路:

首先先回顾下已知的经典情况:

权重$w_i=1$的有界背包最大化问题的LP松弛模型如下:
$$
\begin{align}
&\underset{x}{\max} \sum_i c_i x_i \
& st \sum_i x_i \leq W \
& \forall i, 0\leq x_i \leq n_i
\end{align}
$$
这个问题的最优解策略我已经明确:按照$c_i$从大到小的优先级选取物品即可。

而我当前面临的问题可以表述为如下LP模型:
$$
\begin{align}
&\underset{x, p}{\max} \sum_i c_i x_i \
& st \sum_i x_i \leq W \
& \forall i, 0\leq x_i \leq p_i \
& \lVert p-\hat{p}\rVert_1 \leq \delta
\end{align}
$$
这里的$p$和$\hat{p}$都是概率分布,且满足$W\leq 1$。简单来说,我们可以优化每个物品的选取数量,但$p$与参考分布$\hat{p}$的L1偏差不能超过$\delta$。

新增这个L1偏差约束后,最优解的策略会发生怎样的变化呢?有没有像经典问题那样直观的物品选取规则可以遵循呀?

备注:内容来源于stack exchange,提问作者Lweber17

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.04.16 07:28:12