背包问题 己知一长度b的背包及长度分别为a1,a2,…,an的n 个物品。假定这些物品的半径和背包相同，若从这个物品 中选出若干物品使得恰好装满这个背包。 公式化的描述为：给定一个正整数集A={a1,a2,,an},已 知b是A的某子集中元素的和。问题是，找到一个n元的0、1 向量X=(K1,X2,Xn)使得： 这是一个NP问题。 ∑ax=b i= 其中a1,a2,…，an 和b都是正整数。 13 CNR@HEU http://machunguang.hrbeu.edu.cn背包问题 已知 长度 一 b 的背包及长度分别为 的背包及长度分别为 a1,a2,… ,an 的 n 个物品。假定这些物品的半径和背包相同，若从这 n 个物品 中选出若干物品使得恰好装满这个背包。 公式化的描述为：给定一个正整数集A={a1,a2,…,an 公式化的描 为 给定 个 数集 { 1, 2, , n}，已 知b是A的某子集中元素的和。问题是，找到一个n元的0 、1 向量X=(x1,x2,…,xn)使得： ∑ = n a x b 这是一个NP问题。 ∑ = = i a i x i b 1 13 其中a1, a2, … , an 和 b 都是正整数