0-1背包问题 分支界限法程序 数据结构
实验名称:0-1背包问题 问题描述: 给定n种物品和一个背包,物品i的重量是Wi,其价值为Vi,背包的容量为C。问:应该如何选择装入背包的物品,使得装入背包中物品地总价值最大? 基本要求: 在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入部分的物品i。 (1)调试加入约束函数的回溯法解决此问题。 (2)编写使用分支限界法解决此问题的程序。 测试数据: 这里有n=4种物品,背包容量C=7,w=【3,5,2,1】,这四个物品的单位重量价值分别为【3,2,3.5,4】。
用户评论