一个著名的“难”问题-背包问题 Input:A positive integer b,and positive integers w1,w2,...,wn for some n∈N-{0}. Constraints:M(b,wI,w2,...,wn)={T1nierwi i.e.,a feasible solution for the problem instance b,w1,w2,...,wn is every set of objects whose common weight does not exceed b. Costs: For each TE M(b,w1,w2,...,Wn), cos=ie 优化问题 2U2 简化版本 Goal: maximum. 优化问题 Input: A positive integer b,and 2n positive integers w1,w2,...,Wn.C1, 一般版本 C2,...,cn for some nE NN-10}. Constraints: Mb,w1,…,w,a1,,cm）={T{1,…,n}|∑ierw≤b} T29 Costs: For each T∈M(b,w1,…,Wn,C1,,cm: cost)= Goal: marimum.一个著名的“难”问题 – 背包问题 优化问题 简化版本 优化问题 一般版本