栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

简单博弈(java)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

简单博弈(java)

最近在看左神视频学习算法,记录下比较难懂的有趣的部分

地址:https://www.bilibili.com/video/BV1kQ4y1h7ok?p=10

题目:给定一个整型数组arr,代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌,规定玩家A先拿,玩家B后拿,但是每个玩家每次只能拿走最左或最右的纸牌,玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。

输入:1,2,100,4
输出:101

题目意思是说玩家A和玩家B都做最优决策,最后返回最大分数。

关于这部分看到好多用到记忆化搜索和动态规划的方法,确实比较难懂,本人在这里也只能对照左神的视频谈谈自己的理解,使用暴力法。

从示例输入来看,明牌方式简单分析A,B玩家的博弈心理:

只能从两端取,显然,A只能取1或4,A若取1,B只能取2或4,最后大头100只能拱手相让,A必胜,反过来,A若取4,下一步B必取100,接下来无论如何都是B胜。

从这里来看,这个决策由两部分组成,A先和B后,我们不妨去创建两个方法去模拟A和B的最佳取数的过程

    public static int A(int[]arr,int l,int r)
    {
        if(l == r){  // 如果只有一个待取数了,直接加到上一步总数上
            return arr[l];
        }
        return Math.max(arr[l]+B取最优值后A的最优取值,arr[r]+B取最优值后A的最优取值);  //暴力取法,返回在这一步两端取值情况下的A的最大分数
    }

此时关键是:B取最优值后A的最优取值,这个是关键。

  public static int B(int[]arr,int l,int r)
    {
        if(l == r){ //站在A的角度,最后一个值被B取得,返回0
            return 0;

        }
        return Math.min(f(arr,l+1,r),f(arr,l,r-1));  //此时B若取l值,A就是在l+1到r上做最优取值,
    												//此时B若取r值,A就是在l到r-1上做最优取值
    												//此时为啥是取两者最小
    }

为啥是两者最小??

其实题目中说了A和B都是聪明绝顶的人,故此时B会拿到他的最优取值,故A只能在拿左或拿右中拿到最小的最优取值,A是被B局限的情况下取得最优值

故此时总结构代码为:

public class BoYiLunDemo {

    public static int A(int[]arr,int l,int r)
    {
        if(l == r){
            return arr[l];
        }
        return Math.max(arr[l]+B(arr,l+1,r),arr[r]+B(arr,l,r-1));
    }

    public static int B(int[]arr,int l,int r)
    {
        if(l == r){
            return 0;

        }
        return Math.min(A(arr,l+1,r),A(arr,l,r-1));
    }



    public static void main(String[] args) {
        int[] arr = {1,2,100,4};
        int size = arr.length;
        System.out.println(Math.max(A(arr,0,size-1),B(arr,0,size-1)));
    }
}

打完收工:

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/946323.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号