KnapsackSolve

KnapsackSolve[{cost1,cost2,…},maxtotalcost]

在总成本不大于 maxtotalcost 的约束条件下，求解背包问题，找到与各 costi 关联的物品的最大个数.

KnapsackSolve[{{payoff1,cost1},{payoff2,cost2},…},maxtotalcost]

在满足总成本约束的条件下，求使得总收益最大化的物品数.

KnapsackSolve[{{payoff1,cost1,maxcount1},…},maxtotalcost]

允许物品 i 的个数最多为 maxcounti.

KnapsackSolve[items,{maxtotalpayoff,maxtotalcost}]

求总收益不大于 maxtotalpayoff 的结果.

KnapsackSolve[items,{maxtotalpayoff,maxtotalcost,maxtotalcount}]

添加一个总物品数不大于 maxtotalcount 的约束条件.

KnapsackSolve[label1itemspec1,…,maxtotals]

给各个物品的类型加标签，并以关联的形式给出结果.

更多信息

  • KnapsackSolve 求非负整数计数 ci≤maxcounti 的列表 {c1,c2,…}，使得总收益最大化，并满足由 maxtotals 指定的约束条件.
  • 所有收益和成本必须是非负实数或 Quantity 对象. 计数值必须是非负整数或 Infinity.
  • 约束 maxtotals 的可能规范有：maxtotalcost、{maxtotalcost}、{maxtotalpayoff,maxtotalcost} 和 {maxtotalpayoff,maxtotalcost,maxtotalcount}.
  • 默认情况下，payoffi 的值为 1，最大约束值 Infinity.
  • 如果 maxcounti 被省略或者是 Infinity，KnapsackSolve 求解的是无界背包问题，如果是非负整数，则是有界背包问题，如果全部为 1，则是0-1背包问题.
  • 各个集合 {payoffi,costi,maxcounti} 也可以通过<|"Payoff"->payoffi,"Cost"->costi,"MaxCount"->maxcounti|> 给出，其中项 "Payoff" 和"MaxCount" 是可选的.
  • 约束参数 {maxtotalpayoff,maxtotalcost,maxtotalcount} 也可以通过<|"MaxTotalPayoff"->maxtotalpayoff,"MaxTotalCost"->maxtotalcost,"MaxTotalCount"->maxtotalcount|> 给出，其中项 "MaxTotalPayoff" 和 "MaxTotalCount" 是可选的.

范例

打开所有单元关闭所有单元

基本范例  (4)

求使得总数 c1+c2+c3 最大化并满足 的事物的个数 ci：

在约束条件 下，求使得总收益 3c1+2c2 最大化的物品 c1 和 c2 的个数：

求解关于两组收益、支出和最大数的背包问题：

求解具有额外约束条件总收益与总数目的背包问题：

使用关联给物品集合加标签：

范围  (13)

利润、成本和单独计数  (6)

通过仅指定成本求解背包问题：

忽略的收益被默认被设定为1：

求解背包问题，指定收益和成本值：

通过设定所有最大单独计数为1，得到 0-1 背包问题：

对收益、成本和最大的单独计数命名：

键-值对可以按任意顺序给出：

使用 Association，而不是规则列表：

对物品集合命名：

使用 Association，而不是规则列表：

对两组收益、成本和最大单独计数命名：

总约束条件  (4)

求解具有总成本约束条件的背包问题：

指定关于总收益和总成本的约束条件：

约束总收益、总成本和总数目：

对约束条件进行命名：

键-值对可以按任意顺序给出：

使用 Association，而不是规则列表：

数量和 QuantityArray  (2)

使用 Quantity 对象指定收益或成本：

兼容的单位将自动转换：

求解具有 QuantityArray 对象的背包问题：

数据集  (1)

用 Dataset 对象指定一组事物：

应用  (1)

限定开支，使购物清单中水果的卡路里最大化：

这是各个水果类型的卡路里贡献和总值：

这是各类水果的费用和总费用：

属性和关系  (5)

KnapsackSolve 等价于 LinearProgramming 的一种形式：

如果未指定，总收益值和总计数被设定为 Infinity：

将 maxtotalpayoff 设定为 Infinity 将返回解所能达到的最大总值：

成本和收益可以是非负实数，但计数必须是正整数：

KnapsackSolve 仅返回满足约束条件的一个解：

但其他解也可以存在：

Wolfram Research (2016)，KnapsackSolve，Wolfram 语言函数，https://reference.wolfram.com/language/ref/KnapsackSolve.html.

文本

Wolfram Research (2016)，KnapsackSolve，Wolfram 语言函数，https://reference.wolfram.com/language/ref/KnapsackSolve.html.

CMS

Wolfram 语言. 2016. "KnapsackSolve." Wolfram 语言与系统参考资料中心. Wolfram Research. https://reference.wolfram.com/language/ref/KnapsackSolve.html.

APA

Wolfram 语言. (2016). KnapsackSolve. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/KnapsackSolve.html 年

BibTeX

@misc{reference.wolfram_2024_knapsacksolve, author="Wolfram Research", title="{KnapsackSolve}", year="2016", howpublished="\url{https://reference.wolfram.com/language/ref/KnapsackSolve.html}", note=[Accessed: 22-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_knapsacksolve, organization={Wolfram Research}, title={KnapsackSolve}, year={2016}, url={https://reference.wolfram.com/language/ref/KnapsackSolve.html}, note=[Accessed: 22-November-2024 ]}