背包问题九讲(用蛮力法解决背包问题？)

用蛮力法解决背包问题？

用蛮力求解0/1背包问题，就是列出所有物品装入背包的所有可能性(背包问题的蛮力求解就是穷尽这些物品的所有子集，找出所有可以装入背包的子集，找出这些子集中价值最大的子集)。

背包问题应用实例？

背包问题是一个组合优化的NP完全问题。

背包问题可以描述为：给定一组物品，每个物品都有自己的重量和价格。在有限的总重量内，如何选择才能使物品总价最高？

问题的名称来源于如何选择最合适的物品放入给定的背包中。

类似的问题经常出现在商业、组合数学、计算复杂性理论、密码学和应用数学等领域。

背包问题也可以描述为一个决定性问题，即在总重量不超过W的前提下，总价值能否达到V？它是由Merkle和Hellman在1978年提出的。

背包问题已经被研究了一个多世纪。早期的作品可以追溯到数学家托拜厄斯丹齐格(tobias Dancziger)在1897年的早期作品，它指的是在不超载行李的情况下打包你最有价值或最有用的物品这一常见问题。

背包问题的主要思想是假设某人有大量不同重量的物品。

这个人偷偷挑选一些物品放在背包里，加密消息。

背包里物品的总重量是公开的，所有可能的物品也是公开的，但是背包里的物品是保密的。

附加一定的限制，赋予权重，列出可能的项目，在计算上是不可行的。背包问题是一个众所周知的不可计算问题，背包系统以其快速的加解密速度吸引了人们的注意。

但是背包系统大部分都被破译了，所以用的人很少。

问题 背包 物品 应用 数学

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。