一组不规则的数字拼成一个固定的数字,求指点

蕃薯 发布于 2017/10/30 14:15
阅读 339
收藏 1

有一组不规则的数字4000   7000   2500   3500  3500  2000  1000   4500   3500  6000  8000  1000 

从它们当中随便选一些数字  能拼满10000 就将被使用的数字从数组中剔除,一直到拼不满10000为止

有什么好的算法没,求指点

 

加载中
1
flyingsam
flyingsam
public class TenThousand {

    public static void main(String[] args) {
        Integer[] numbers = new Integer[]{4000, 7000, 2500, 3500, 3500, 2000, 1000, 4500, 3500, 6000, 8000, 1000};
        List<Integer> numberList = new ArrayList<Integer>(Arrays.asList(numbers));
        System.out.println("array : " + numberList);


        Random random = new Random();

        int sum = 0;
        Map<Integer, Integer> select = new HashMap<Integer, Integer>();
        while (true) {
            int i = random.nextInt(numberList.size());
            if (select.containsKey(i)) {
                continue;
            }
            select.put(i, numberList.get(i));
            sum += numberList.get(i);

            if (sum == 10000) {
                System.out.println("equal 10000 index:" + select.toString());
                for (int s : select.keySet()) {
                    System.out.println("remove value : " + select.get(s));
                    numberList.remove(select.get(s));
                }
                sum = 0;
                select.clear();
                System.out.println("new array : " + numberList);
            } else if (sum > 10000) {
//                System.out.println("greater than 10000:" + select.toString());
                sum = 0;
                select.clear();
            }
        }


    }
}

用java实现了

疏影横斜
疏影横斜
这样 可能永远不会得到结果~
1
疏影横斜
疏影横斜

这个最简单的就是用递归,

取第一个数,然后

for(剩下得数)

{

第一个数+剩下的数[i]

if(>10000){

不能和第二个数相加,就去找第三个数

}else{

接着取第三个数相加

}}

基本思路就是这样,算法自己实现~

疏影横斜
疏影横斜
回复 @DXCyber409 : 还有一个比较好的思路, 先取一个数,看有没有==10000的,if(都大于10000),结束;else 继续; 在逐个取两个数相加 ,if(都大于10000),结束;else 继续; ....一次进行下去~~
疏影横斜
疏影横斜
回复 @DXCyber409 : 数量不是很多,不至于栈溢出~
DXCyber409
DXCyber409
运气不好的话可能会栈溢出
0
蓝风970655147
蓝风970655147

是要, 找出最多的对数, 还是每次随机抽取 

蕃薯
蕃薯
随机,只要能凑成10000就行
0
OSC_wwukcN
OSC_wwukcN
虽然我不会,但我还是希望能把条件描述更准确些,是==10000还是,>=10000
0
inuxor
inuxor

如果给出的数值如题主范例的那样规整,完全是1000<=x<=9500的500整数倍,问题其实可以简化为:

穷举2~19范围内和为20的组合

0
polly
polly
先正序排序。 随机取一个,从前往后找,如果找到了,后面的和你拼起来都满足。 找的过程,可再考虑二分查找
返回顶部
顶部