java程序动态规划凸三角划分01背包

《java程序动态规划凸三角划分01背包》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验报告6课程数据结构与算法实验名称动态规划第页班级11计本学号105032011117姓名风律澈实验日期：2013年4月8日报告退发(订正、重做)一、实验目的掌握动态规划策略的原理和应用。二、实验环境1、微型计算机一台2、WINDOWS操作系统，JavaSDK，Eclipse开发环境三、实验内容必做题：1、编写程序，求一个多边形最优剖分的最优值和最优解，最优值是剖分而得的三角形权值之和的最大值，最优值对应的最优解是一个弦的集合，两个顶点对代表一根弦，输出这个集合的每个元素。三角形权值的计算：通过一个二维数组w，给出任意两个顶点(i,j)连线的权值为w[i][j]，三角形的权值为

2、构成该三角形的三条连线的权值之和。2、编写程序，求0-1背包问题的最优值和最优解，最优值是背包所能容纳物品的最大价值，最优值所对应的最优解是一个物品的集合，输出集合中每件物品的编号。四、实验步骤和结果1、三角剖分问题publicclassMinWeightTriangulation{/***@paramargs*/publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubintv[]={0,1,2,3,4,5};//顶点ints[][]=newint[v.length][v.length];//定义记录数组，

3、为了回寻最佳分割点intt[][]=newint[v.length][v.length];//定义存贮数组，用于避免重复计算//填数组minweight(v,s,t);//输出System.out.println(t[1][v.length-1]);scout(s,1,v.length-1);}privatestaticvoidscout(int[][]s,inti,intj){//TODOAuto-generatedmethodstubif(i==j)return;scout(s,i,s[i][j]);scout(s,s[i][j]+1,j);System.out.printl

4、n("v"+(i-1)+"and"+"v"+j+"and"+"v"+s[i][j]+";");}privatestaticvoidminweight(int[]v,int[][]s,int[][]t){//TODOAuto-generatedmethodstubintn=v.length-1;for(inti=0;i<=n;i++)//初始化对角线t[i][i]=0;for(intr=2;r<=n;r++)//填对角线以上的空位for(inti=1;i<=n-r+1;i++)//i从1～5{intj=i+r-1;//j是对角线下一个t[i][j]=t[i+1][j]+w(i-1,

5、i,j);s[i][j]=i;for(intk=i+1;k

6、s*/publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubintwei[]={2,2,6,5,4};intvalue[]={6,3,5,4,6};intcnum=10;intm[][]=newint[wei.length+1][cnum+1];//填mknapsack(wei,value,m,cnum);//输出System.out.println(m[wei.length][cnum]);ncout(m,wei,cnum);}privatestaticvoidncout(int[][]m,int[]w

7、ei,intcnum){//TODOAuto-generatedmethodstubintj=wei.length;inti=cnum;while(j!=0){if(m[j][i]!=m[j-1][i]){System.out.print(j+"");j--;i=i-wei[j];}elsej--;}}privatestaticvoidknapsack(int[]wei,int[]value,int[][]m,intcnum){//TODOAuto-generatedmethod