算法: 找子集合并按权值和排序 (货郎有关问题辅助算法)

算法: 找子集合并按权值和排序 (货郎问题辅助算法)

假设给出的 1-8 个数, 选4个

1) 最小的权值的几个 ( 1, 2, 3, 4)

2) 假设当前(a, b, c, d),  如果我们能确定权值和刚好大过它的组合, 不难找到所有组合按权值和排序

数据结构

需要两个结构 selects和 remains,  selects 是已经选择的子集合, remains 是要考虑的数

他们是列表并需要排序, 先开始元素放置如下

算法

1) 用 remains 中最小的元素到 selects 中找到刚好它能大过的元素

2) 如果找到, 交换这两个元素

3) 如果不能找到, 从 remains 中删除此元素, 取下一个元素继续找 ( 就是到 1) )

------------ 能找到的情况

selects

remains

selects

remains

------------ 不能找到的情况

selects

remains

selects

remains

( 1 不用在考虑了, 放入 selects 必然会造成权值减少 )

================= 具体程序如下 ==================

package com.pnp.findnextnumber;import java.util.ArrayList;import java.util.Collections;public class NextWeighSum {    ArrayList<Integer> remains = new ArrayList<Integer>();    ArrayList<Integer> selects = new ArrayList<Integer>();    int TOTAL_COUNT = 10;    int SELECT_COUNT = 4;    void init() {        for( int i=0; i<TOTAL_COUNT; i++)            remains.add(i+1);        Collections.sort(remains);        for (int i=0; i<SELECT_COUNT; i++)            selects.add( remains.remove(0));    }        /*     * selects give the subset, need to return the next subset which the weight sum is just larger than current subset       */    boolean selectNext() {        while( remains.size() > 0) {            int cur = remains.get(0);            int pos = Collections.binarySearch(selects, cur);            if (pos < 0) // binarySearch (-(insertion point) - 1)                pos = (-pos) -1;            else {                System.err.print("Not allow equal elements");                System.exit(-1); // Not allow equal elements            }                        if ( pos == 0 )  {// that means current element is less that any in selects, we won't need to consider this elem                remains.remove(0);                continue;            }            else {                int insert_pos = pos-1;                remains.set(0,selects.get(insert_pos));                selects.set(insert_pos, cur);                System.out.print(" an select ---");                print(selects);                return true;            }        }        return false;    }        void selectAll() {        while (selectNext())            ;    }    static void print(ArrayList<Integer> list ) {        int sum = 0;        for (int i=0; i< list.size(); i++) {            sum += list.get(i);            System.out.print( " " + list.get(i));        }        System.out.println("   sum:"+sum  );    }    public static void main(String[] args) {        NextWeighSum m = new NextWeighSum();        m.init();        m.selectAll();    }}

这个算法打算在 "货郎问题" 中使用, 货郎问题是选择权值和最小的边集合,试探是否其构成路径. 构成则问题解决,否则试探下一个.