链接：https://pan.baidu.com/s/158fiJd4NYeqGi-h_k9AcWQ 

提取码：b172 

 

一、实验目的

熟练掌握贪心法的设计思想与技巧。

二、实验内容

设计、编写程序，理解贪心法的实现过程，深入理解贪心法与动态规划法的区别。调试、运行程序，观察、记录结果并分析。

 

 

 

三、实验分析与实现

1.我用的模型和我的实验二一样，如下图所示：

 

2.只不过这样体现不出来贪心算法，事实上它也算贪心算法，是按照i的大小的贪心，可是这种贪心只需要对整个数组从上到下遍历就可以了。因此我们定的贪心标准一定要和i无关，因此可以对路径分配权重。

3.现规定每条路径的权重为开始点的值，例如2->4的权重是2.找一条路径末端数字为tres，且权值最小的路径。

4.整个算法的主体部分是一个for循环，其中套有5个for循环（已在代码中用//1~5标注）。

5.第一个for循环是在找到第一个符合要求的tres之前，为了找tres。因为在没找到第一个tres时，只需要遍历数组找tres，不需要维护tmp数组。需要注意的是在第i层找到了tres，不能break，不能找第一个tres，要把i层找完，找权值最小的tres，不然的话对i层的tmp会覆盖几次值，不简便。

6.第二个for循环可以合并到第三个for循环中，任务是维护tmp数组。

7.第四个for循环当第i层的权重都大于等于当前权重时停止查找，此处体现贪心思想。

8.第五个for循环当找到权值更小的tres时，更新tmp数组，更新的方法是将第i层全都减去新旧权值之差的绝对值。

 

四、实验过程中的问题及对应思考

第一个问题就是上述分析第5点，一开始写的是找第一个tres，出了点问题，后来调整过来了。第二个问题是一开始我令tmp=-1代表不可行，后来发现tmp<0就可以了，这样一来当维护tmp时将tmp值减到0以下就可以直接判断，不用再写if语句赋值。第三个问题是纠结了一会是否要保存行row和列col，行row可以不需要（要按照上述分析第6点那样合并），列col在每一行都要更新。不需要创建greed的全局副本，只要在第五个for循环中创建greed副本以计算差值就可以了，其它地方可以直接修改greed。

 

五、附录

编译器eclipse

 

Solution

public int greedMinPath(int[][]tr,int tres) {//tr内存放的数不仅是key，还是代价权重

//int res=-1;

int greed=10005;

int row=-1;

 

int [][]tmp=new int[tr.length][tr.length];

boolean find=false;

for(int i=0;i<tr.length;i++) {

if(!find)

for(int j=0;j<=i;j++) {//1

if(tr[i][j]==tres&&greed>getPath(tr,i,j)) {

greed=getPath(tr,i,j);

row=i;

//col=j;

find=true;

}

}

//res=greed;

if(find) if(i==row)

for(int j=0;j<=i;j++) { //2

tmp[i][j]=greed-getPath(tr,i,j);

}

else {

int col=-1;

for(int j=0;j<=i;j++) {//3

if(j==0) {

tmp[i][j]=tmp[i-1][j]-tr[i-1][j];

}

else if(j==i) {

tmp[i][j]=tmp[i-1][j-1]-tr[i-1][j-1];

}

else{

tmp[i][j]=Math.max(tmp[i-1][j]-tr[i-1][j], tmp[i-1][j-1]-tr[i-1][j-1]);

}

}

boolean end=true;

int max=-1;

 

for(int j=0;j<=i;j++) {//4

if(tmp[i][j]!=-1) {

end=false;//能往下找

if(tr[i][j]==tres&&tmp[i][j]>max) {

max=tmp[i][j];

row=i;

col=j;

}

}

}

if(end) break;

if(col!=-1){//有找到

int copy=greed;

greed=getPath(tr,row,col);

int cha=copy-greed;

for(int j=0;j<=i;j++) {//5

tmp[i][j]-=cha;

}

}

}

 

}

return greed==10005?-1:greed;

}