算法背包问题
发布时间：2023-05-08 08:51:44
精选文档实验题目：背包问题
实验目的：掌握动态规划、贪心算法的原理，并能够按其原理编程实现解决背包问题，以加深对上述方法的理解。
实验内容：一个旅行者准备随身携带一个背包.可以放入背包的物品有n种,每种物品的重量和价值分别为wj,vj.如果背包的最大重量限制是b,怎样选择放入背包的物品以使得背包的价值最大?
n目标函数：
maxvjxjj1约束条件：线性规划问题
wj1njxjb,xjN由线性条件约束的线性函数取最大或最小的问题整数规划问题线性规划问题的变量xj都是非负整数
Fk(y：装前k种物品,总重不超过y,背包的最大价值
i(k,y：装前k种物品,总重不超过y,背包达最大价值时装入物品的最大标号
Fk(ymax{Fk1(y,Fk(ywkvk}F0(y0,0yb,Fk(00,0kn递推方程、边界条件、标记函数
yF1(yv1w1
实例计算：v1=1,v2=3,v3=5,v4=9,w1=2,w2=3,w3=4,w4=7,b=10
Fk(y的计算表如下:K/y1
2345678910Fk(yy0.
精选文档
12340000111113332355245536663689474959
101011101012
实验步骤：1、分析题目；
2、打开NetBeans软件，新建一个名叫Knapsackdxj的项目，并对其进行保存；3在新建的项目下对我们所分析的题目进行编写； 