# 背包的可行性问题 背包的可行性问题就是对于一个背包问题，是否存在某种形式的解。 比如对于一个普通的01背包，询问是否存在可以**完全装满**背包的方法。 ## 经典问题 ### 题面描述 有两个海盗，他们得到了一箱宝石。 每一颗宝石都有自己的价值​，每一颗宝石必须属于且仅能属于一个海盗。 现在两个海盗想平分这些宝石，但是他们不知道怎么分，现在他们来请教你了。 ### 分析 假设所有珠宝的总价值为sum​，那么sum显然​必须是偶数。两个海盗平分也就是说一人得到​的珠宝价值为sum/2。这相当于用一个容积为​sum/2的背包来装这些宝石，如果背包的最大价值为sum/2，那么就存在一种方法，使得两个海盗平分这些珠宝。 ### 复杂度及代码 时间复杂度：O(n\*sum/2) 空间复杂度：O(n\*sum/2) 代码与01背包类似。