首页 > 试题广场 >

利用回溯法求下列不等式的所有整数解的个数为：（）

[单选题]
利用回溯法求下列不等式的所有整数解的个数为：（）
3*1+4*2+2*3<=12,其中x1，x2，x3为非负整数 
  • 34
  • 30
  • 32
  • 31
查看正确选项
添加回答
Vanellope头像 Vanellope

1、什么时回溯法？

回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。

2、回溯法java代码实现： 

/**  * Created by FHY on 2019/3/19\.  
* 回溯法实现 
*/ 
public class BackDateDemo { 
    public static void main(String[] args){ 
        //定义一个布尔矩阵，用于判断该x1, x2, x3序列是否已存在  
        boolean[][][] visited = new boolean[5][4][7]; 
        int count = getCount(0, 0, 0, visited);
        System.out.println("符合条件的结果共："+count);
    } 

    //回溯法实现所有结果的列出  
    public static int getCount(int x1, int x2, int x3, boolean[][][] visited){ 
        int result = 0; 
        if(x1 > 4 || x2 > 3 || x3 > 6 || visited[x1][x2][x3]) 
            return result; 
        if(3 * x1 + 4 * x2 + 2 * x3 12){
            visited[x1][x2][x3] = true;
            System.out.println("3*"+x1+"+4*"+x2+"+5*"+x3+"="+(3 * x1 + 4 * x2 + 2 * x3));
            result = 1+ getCount(x1+1, x2, x3, visited) + 
                        getCount(x1, x2+1, x3, visited) + 
                        getCount(x1, x2, x3+1, visited);
        } 
        return result;
    }
}
部分输出结果如下：
 3*0+4*0+5*0=0
 3*1+4*0+5*0=3
 3*2+4*0+5*0=6
 3*3+4*0+5*0=9
 3*4+4*0+5*0=12
 3*3+4*0+5*1=11
 3*2+4*1+5*0=10
 3*2+4*1+5*1=12
编辑于 2019-03-19 17:16:58 回复(0)
视觉算法工程师头像 视觉算法工程师
发表于 2017-09-06 17:40:59 回复(0)
luffymaika头像 luffymaika 
sum = 0
for i in range(5):
    for j in range(4):
         for x in range(7):
             if 3*i+4*j+2*x<=12:
                sum++;
发表于 2018-03-27 12:34:00 回复(3)
公司倒闭了吗？头像 公司倒闭了吗？

回溯法类似于深度优先遍历

发表于 2019-10-30 01:00:54 回复(0)
额图腾头像 额图腾
什么叫做回溯法？有人解释一下吗？
发表于 2018-08-29 11:12:50 回复(1)
jokervsbat头像 jokervsbat
这题有多么公式之类的吗？
发表于 2017-08-17 10:11:56 回复(0)
提交观点

问题信息

dfs
来自：乐视2017秋招开发工...
上传者：牛100
难度：
6条回答 10934浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号