问题描述
在一条公路上埋有若干堆地雷，每堆地雷有一定的数量，地雷堆的编号为1，2，…，N，例如，埋有地雷数量如下：8 14 2 17 33 26 15 17 19 6此时，地雷的数量可用一维数组A(N)表示。同时，给出地雷堆之间的联系，从第1堆开始，它指出挖了此堆之后，还可以选择继续往下挖，若存在多种方案，只能选择其中的一种，若没有任何后继的方案，则挖地雷结束。例如，可给出下面的关系:
地雷堆之间的联系可用以下的数组表示:
二维整数型数组R(I，J)表示，当R(I，J)=1表示从I到J有通路，当R(I，J)=0表示无通路。上图的R如下所示：
最终，找出可以挖到地雷的最大值
DP
主要思想
其实刚开始看到这个地雷图就想到了DAG问题。下面就用动态规划求解这个问题。对于第i堆地雷来说，选择能够挖最多的那条路径，就是下面这个递推公式。dp[i][j]表示i到j上的最大值，但是只有通过和i相连的那些路径才能够通向更远。因为是单向图，所以在这里，填表要从下向上填表。
dp[i][j]=a[i]+max{dp[m][j],R[i][m]=1且m<=j}
Java代码实现
/
* 求最大地雷数
* @param a ai表示第i堆的地雷个数
* @param r r(i,j)表示i和j之间是否存在通路
*/
public static void getMax(int[]a,int[][]r) {
int n=r.length;//个数
int[][] dp=new int[n][n];//dp(i,j)表示i到j之间可以挖到的最大数量
int[][]path=new int[n][n];
//初值
for(int i=0;i
dp[i][i]=a[i];
path[i][i]=i;
}
for(int i=0;i
for(int j=i+1;j
if(r[i][j]==1)
{
dp[i][j]=a[i]+a[j];
path[i][j]=j;
}else {
path[i][j]=-1;
}
}
}
//填表,从下方开始填表
for(int i=n-1;i>=0;i--) {
for(int j=i+1;j
for(int m=0;m<=j;m++) {
if(r[i][m]==1)
{
//dp[i][j]=Math.max(a[i]+dp[m][j],dp[i][j]);
int temp=a[i]+dp[m][j];
if(temp>dp[i][j])
{
dp[i][j]=temp;
path[i][j]=m;
}
}
}
}
}
//找到表中的最大值
int max=0,x = 0,y = 0;
for(int i=0;i
for(int j=i;j
if(max
{
max=dp[i][j];
x=i;y=j;
}
}
}
//输出最优解
System.out.println("先挖第"+(1+x)+"堆");
while(x!=y) {
x=path[x][y];
System.out.println("再向下挖第"+(1+x)+"堆");
}
System.out.println("最多挖到"+max+"堆雷");
}
public static void main(String[] args) {
Scanner scn=new Scanner(System.in);
int n=scn.nextInt();//个数
int[]a=new int[n];
for(int i=0;i
a[i]=scn.nextInt();
}
int[][]r=new int[n][n];
for(int i=0;i
for(int j=i+1;j
r[i][j]=scn.nextInt();
}
}
getMax(a,r);
}
运行结果
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/48295.html