算法背包问题

《算法背包问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验题目：背包问题实验目的：掌握动态规划、贪心算法的原理，并能够按其原理编程实现解决背包M题，以加深对上述方法的理解。实验内容：一个旅行者准备随身携带一个竹可以放入竹的物品有n种，每种物品的重量和价值分别为wj，vj.如果背包的最大重量限制是b，怎样选择放入背包的物品以使得背包的价值最大？0标函数：约朿条件：线性规划问题maxv..X由线性条件约束的銭或最小的问题整数规划问题线性规划问题的变量xj都是非负整数Fk(y):装前k种物品，总重不超过y,背包的最大价值i(k,y):装前k种物品，总重不超过y,背包达最大价值吋装入物品的

2、最大标号递推方程、边界条件、标记函数()，)=max{FA._,(y),()’-wk)+vk}F0(y)=0,0

3、3在新建的项目卜*对我们所分析的题目进行编写;4、调试所编写的程序；5、运行文件，并对其进行测试，看是否正确。实验结果：轮出•Chap4(run)XH>

4、run:~Lt.请筘入背包铊够承受的总芏量:诗玲入可以装入背包的笱品的种类：纷3请筘入3种初品中与一种初品的2量和价值:7152411可装入笱品的鼉大价值为：27第1个初品放入1样笫2个初品放入3样笫3个钓品放入0样成功构注(总时间：23秒〉实验小结：在做本次实验之前，Q己对动态规划、贪心算法的原理不是非常的理解，花了很多时间看了课本上的相关内容。当你懂得算法的基本原理后，再参

5、考老师所提供的代码进行完善补充，必须结合算法的实际情况对代码屮的相关变量进行修改，这样才能充分利用课木所提供的代码完成木次实验。通过木次试验，G己基木上掌握上述算法解背包问题的原理，达到实验的目的。实验代码：Knapsack.Javapackagechap4;importjava.util.Scanner;氺氺@authorJinyupublicclassKnapsack{//•ii•*—ffn~^賣置-UI■.fstaticfinalintMAX_NUM=20;staticfinalintMAXJVETGHT=100;//

6、氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺Qg氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺//氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺yirriiii^t4氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺氺privatefinalintweight[]=newint[MAX_NUM];privatefinalintvalue[]=newint[MAX_NUM];privatefinalintx[]=newint[MAX_NUM];privatefinalprivatefinalintm[][]=newint[MAX_NUM]

7、[MAX_NUM];ints[][]=newint[MAX—NUM][MAX—NUM];privateintn;privateintw;inth;int1;ff■■【JIf.暑•III//^p^p^p^p^p^p^p^p^p^p•jT'd.Vx•、J▲Ll/p^p^p^p^p^p^p^p^p^p^p^p^p^p^p^p^p^p^p^p^p^p^p^p^p^p^p^p^p^ppublicvoidsolve()intk=1;inta=1;for(inti=1;i<=n;i++){for(intj=1;j<=w;j++){k=1;i

8、f(weight[i]〈=j){h=weight[i];1二value[i];while(h<=j&&a==1){//判断是否能够装入h=weight[i]*k;//k是放入物品的次数，每放一次，k加1再重新判断是杏还能放进1=value[i]*k;//System,out.printIn(h+，zd，/);if(m[i-1][j]>m[i-1][j-h]+1

9、

10、m[i][j]>(m[i-1][j-h]+1)){//判断是否应该装入if(k==1){//第一次的时候才执行不放入的操作，k不等于1的时候保持上一次操作的结果不进行改

11、变m[i][j卜m[i-l][jh//不装入s[i][j]=0;}a=0;}else{m[i][j]=m[i-1][j-h]+1;//应该装入s[i][j]=k;//存放装入次数，用于求最优解k++;//装入后k加1h=weight[i]本k;1二value[i