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

假设给出的 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

1 2 3 4
5 6 6 8

remains

selects

1 2 3 5
4 6 6 8

remains

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

selects

2 3 4 5
1 6 7 8

remains

selects

2 3 4 5
6 7 8

remains

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

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

[java]
package com.pnp.findnextnumber;

import java.util.ArrayList;
import java.util.Collections;

public class NextWeighSum {

ArrayList remains = new ArrayList();
ArrayList selects = new ArrayList();
int TOTAL_COUNT = 10;
int SELECT_COUNT = 4;

void init() {
for( int i=0; i remains.add(i+1);
Collections.sort(remains);
for (int i=0; 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 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();
}

}

package com.pnp.findnextnumber;

import java.util.ArrayList;
import java.util.Collections;

public class NextWeighSum {

ArrayList remains = new ArrayList();
ArrayList selects = new ArrayList();
int TOTAL_COUNT = 10;
int SELECT_COUNT = 4;

void init() {
for( int i=0; i remains.add(i+1);
Collections.sort(remains);
for (int i=0; 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");