分酒问题(DFS解法)

分酒问题(DFS解法)题目大概是这样:已知有三个容量分别为3千克、5千克和8千克的并且是没有刻度的酒瓶,3千克和5千克的瓶子均装满了酒,而8千克的瓶子为空。现要求仅用这三个酒瓶将这些酒均分为两个4千克并分别装入5千克和8

大家好,又见面了,我是你们的朋友全栈君。

题目大概是这样:

已知有三个容量分别为3千克、5千克和8千克的并且是没有刻度的酒瓶,3千克和5千克的瓶子均装满了酒,而8千克的瓶子为空。现要求仅用这三个酒瓶将这些酒均分为两个4千克并分别装入5千克和8千克的瓶子中。

题解:

可以扩展为有n个瓶子,每个瓶子当前装了x1,x2,x3…xn的酒,每个瓶子的上限是y1,y2,…yn,目标状态是每个瓶子d1,d2,…dn,现在要从当前状态转换到目标状态

可以解读到,每个瓶子只有两种状态–要么盛满,要么空

所以当酒从x瓶子转移到y瓶的时候,只有可能是试图将酒全部到入y瓶中,这样会造成两种结果:

  能盛得下– x瓶空,y瓶的酒为原来的酒加上x瓶原来的酒。

  盛不下– x瓶的酒为原来的酒减去倒过去的那部分, y瓶满。

很显然,如果要求最短的步数,BFS是一个比较简单的办法,现在想输出所有的路径,所以考虑DFS

代码:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//已知有3个容量分别为3kg,5kg和8kg且没有刻度的酒瓶3kg和5kg的瓶子均装满了酒。而8kg的瓶子为空。
//现要求仅用这3个酒瓶将这些酒均分为两个4kg,并分别装入5kg和8kg的瓶子中。

public class DispensingProblem {
    public static int N;  //酒瓶的数量
    public static Integer[] bottleMax;  //每个酒瓶最多装多少酒
    public static Integer[] bottleCurrent;  //每个酒瓶现在装了多少酒
    public static Integer[] bottleFinal;   //标注每个酒瓶的最终状态
    public static ArrayList<String> states;   //标注每一种状态,防止重复(每一种状态是一个向量,我用整型数组表示)
    public static ArrayList<String[]> paths;   //标注每一条路径
    public static int caseNum = 0;   //标注是第几种方法
    public static int minNum = 1000000;  //标注最少需要的步数
    public static void dfs(int n){
        String testS = String.valueOf(bottleCurrent[0]);
        for(int m =1;m<N;m++)
            testS+=String.valueOf(bottleCurrent[m]);
        boolean flag = true;
        for(int k = 0;k<N;k++)
            if(bottleCurrent[k]!=bottleFinal[k])
                flag = false;
        if(flag){
            caseNum ++ ;
            if(n <= minNum){
                if(n<minNum){
                    paths.clear();    
                }
                String[] tempS= new String[states.size()];
                for(int ll = 0;ll<states.size();ll++)
                    tempS[ll] = states.get(ll);
                paths.add(tempS);
                minNum = n;
            }
            System.out.println("第"+caseNum+"种方法:");
            for(int l=0;l<states.size();l++)
                System.out.println(states.get(l));
            System.out.println("总共需要移动"+n+"步");
            System.out.println("------------------------------------");
            return;
        }
        //找出当前可能的所有移动
        //数据不大,不需要优化
        //每个瓶子只能倒满或者倒空
        //注意要标注每一种状态,防止状态重复
        for(int i = 0 ; i < N;i++)
            for(int j = 0; j < N ;j++){
                if(i==j)
                    continue;
                //从i瓶把所有酒倒入j瓶
                int nI = bottleCurrent[i];
                int nJ = bottleCurrent[j];
                int temp = nI + nJ - bottleMax[j];
                if(temp<=0){
                    //能全倒进去
                    bottleCurrent[i] = 0;
                    bottleCurrent[j] = nI + nJ;
                    String s = String.valueOf(bottleCurrent[0]);
                    for(int m =1;m<N;m++)
                        s+=String.valueOf(bottleCurrent[m]);
                    if(!states.contains(s)){
                        states.add(s);
                        dfs(n+1);
                        //回溯
                        states.remove(states.indexOf(s));
                    }
                    //回溯
                    bottleCurrent[i] = nI;
                    bottleCurrent[j] = nJ;
                }
                else{
                    //不能全倒进去
                    bottleCurrent[i] = temp;
                    bottleCurrent[j] = bottleMax[j];
                    String s = String.valueOf(bottleCurrent[0]);
                    for(int m =1;m<N;m++)
                        s+=String.valueOf(bottleCurrent[m]);
                    if(!states.contains(s)){
                        states.add(s);
                        dfs(n+1);
                        //回溯
                        states.remove(states.indexOf(s));
                    }
                    //回溯
                    bottleCurrent[i] = nI;
                    bottleCurrent[j] = nJ;
                }
            }
        //找遍所有状态都不可行,则表明不能出现这种状态
        //System.out.println("不可能存在这种状态!");
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入瓶子个数");
        N = sc.nextInt();
        bottleMax = new Integer[N];
        bottleCurrent = new Integer[N];
        bottleFinal = new Integer[N];
        states = new ArrayList<String>();
        paths = new ArrayList<String[]>();
        System.out.println("请输入每个瓶子的容量");
        for(int i = 0 ;i < N; i ++){
            bottleMax[i] = sc.nextInt();
        }
        System.out.println("请输入每个瓶子当前有多少酒");
        for(int i = 0 ;i < N; i ++){
            bottleCurrent[i] = sc.nextInt();
        }
        System.out.println("请输入最终希望每个瓶子有多少酒");
        for(int i = 0 ;i < N; i ++){
            bottleFinal[i] = sc.nextInt();
        }
        String s = String.valueOf(bottleCurrent[0]);
        for(int i =1;i<N;i++)
            s+=String.valueOf(bottleCurrent[i]);
        states.add(s);
        dfs(0);
        System.out.println("******************************");
        System.out.println("最少需要"+minNum+"步");
        int index = 0;
        for(int i = 0;i<paths.size();i++){
            index++;
            System.out.println("第"+index+"种最短方法:");
            String[] temp = paths.get(i);
            for(int j = 0;j<temp.length;j++)
                System.out.println(temp[j]);
            System.out.println("-----------------------------------");
        }
        System.out.println("******************************");
    }
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/155420.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号