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

实验报告6课程 数据结构与算法 实验名称 动态规划 第 页班级 11计本 学号 105032011117 姓名 风律澈 实验日期：2013年4月8日 报告退发 (订正 、 重做) 一、实验目的掌握动态规划策略的原理和应用。二、实验环境1、微型计算机一台 2、WINDOWS操作系统，Java SDK，Eclipse开发环境三、实验内容 必做题：1、 编写程序，求一个多边形最优剖分的最优值和最优解，最优值是剖分而得的三角形权值之和的最大值，最优值对应的最优解是一个弦的集合，两个顶点对代表一根弦，输出这个集合的每个元素。三角形权值的计算：通过一个二维数组w，给出任意两个顶点(i,j)连线的权值为wij，三角形的权值为构成该三角形的三条连线的权值之和。2、 编写程序，求0-1背包问题的最优值和最优解，最优值是背包所能容纳物品的最大价值，最优值所对应的最优解是一个物品的集合，输出集合中每件物品的编号。4、 实验步骤和结果1、 三角剖分问题public class MinWeightTriangulation /* * param args */public static void main(String args) / TODO Auto-generated method stubint v=0,1,2,3,4,5;/顶点int s=new intv.lengthv.length;/定义记录数组，为了回寻最佳分割点int t=new intv.lengthv.length;/定义存贮数组，用于避免重复计算/填数组minweight(v,s,t);/输出System.out.println(t1v.length-1);scout(s,1,v.length-1);private static void scout(int s, int i, int j) / TODO Auto-generated method stubif(i=j)return;scout(s,i,sij);scout(s,sij+1,j);System.out.println(v+(i-1)+ and +v+j+ and +v+sij+;);private static void minweight(int v, int s, int t) / TODO Auto-generated method stubint n=v.length-1;for(int i=0;i=n;i+)/初始化对角线tii=0;for(int r=2;r=n;r+)/填对角线以上的空位for(int i=1;i=n-r+1;i+)/i从15int j=i+r-1;/j是对角线下一个tij=ti+1j+w(i-1,i,j);sij=i;for(int k=i+1;kj;k+)int u=tik+tk+1j+w(i-1,k,j);if(utij)tij=u;sij=k;private static int w(int i, int i2, int j) / TODO Auto-generated method stubint l,m,n;l=i2-i;m=j-i2;n=j-i;if(l0)l=-l;if(m0)m=-m;if(n0)n=-n;return (l+m+n);2、01背包问题public class Bag01 /* * param args */public static void main(String args) / TODO Auto-generated method stubint wei=2,2,6,5,4;int value=6,3,5,4,6;int cnum=10;int m=new intwei.length+1cnum+1;/填mknapsack(wei,value,m,cnum);/输出System.out.println(mwei.lengthcnum);ncout(m,wei,cnum);private static void ncout(int m, int wei,int cnum) / TODO Auto-generated method stubint j=wei.length;int i=cnum;while(j!=0)if(mji!=mj-1i)System.out.print(j+ );j-;i=i-weij;elsej-;private static void knapsack(int wei, int value, int m, int cnum) / TODO Auto-generated method stub/init mfor(int i=0;icnum+1;i+)m0i=0;for(int i=0;iwei.length+1;i+)mi0=0;/开始放入int t;for(int i=1;iwei.length+1;i