0—1背包问题描述如下： 给定m种物品和一背包。物品i的重量是w[i]，其价值为v[i]，背包的容量是c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。(每种物品只能选择放入0/1次背包）-0-1 knapsack problem described as follows: given m types of items and a backpack. Item i of the weight of w [i], a value of v [i], the capacity

背包问题扩展——解公司外包成本问题 小米所在的公司需要至少W个其他公司提供的外包人员，现在有N家公司向小米的公司提供了可选方案，其中 Pi代表可提供外包人员单位数，如5人为一个单位数，若选用该公司方案，则必须采用整单位数的人数，如5人为一个单位数，则X公司只能采用n*5个人数（n=0,1,2,….)。Ci代表为Pi单位数员工提供的总工资，单位是万元 输入格式： N W Pi C i 请问，采取什么样的方案可以满足公司花最少的开销招到至少W个外包人员，求出最少的开销金额。