日期:2014-05-20 浏览次数:21305 次
public static void main(String[] args) {
List<List<Integer>> re = op(1, 5, 3, 3);
if (re == null) {
System.out.println("error");
return;
}
for (List<Integer> tl : re) {
for (Integer n : tl) {
System.out.print(n + ",");
}
System.out.println("");
}
}
static List<List<Integer>> op(final int min, final int max, final int age, final int count) {
List<List<Integer>> tn = new ArrayList<List<Integer>>();
{//初始化
int sum = age * count;
//确定最大边界
int bmax = sum - min * (count - 1);
bmax = Math.min(bmax, max);
//最小边界
int bmin = sum - max * (count - 1);
bmin = Math.max(bmin, min);
if (bmax < bmin) {
return null;
}
for (int i = bmin; i <= bmax; i++) {
List<Integer> nl = new ArrayList<Integer>();
nl.add(i);
tn.add(nl);
}
}
for (int i = 1; i < count; i++) {
List<List<Integer>> btn = new ArrayList<List<Integer>>();
for (int j = 0, jm = tn.size(); j < jm; j++) {
List<Integer> nl = tn.get(j);
int sum = count * age;
for (Integer item : nl) {
if (item == null) {
break;
}
sum -= item;
}
//确定最大边界
int bmax = sum - min * (count - i - 1);
bmax = Math.min(bmax, max);
//最小边界
int bmin = sum - max * (count - i - 1);
bmin = Math.max(bmin, min);
for (int z = bmin; z <= bmax; z++) {
List<Integer> bnl = new ArrayList<Integer>();
bnl.addAll(nl);
bnl.add(z);
btn.add(bnl);
}
}
tn = btn;
}
//排序
for (List<Integer> l : tn) {
Collections.sort(l);
}
Collections.sort((List) tn, new Comparator<List<Integer>>() {
public int compare(List<Integer> o1, List<Integer> o2) {
for (int i = 0; i < o1.size(); i++) {
if (!o1.get(i).equals(o2.get(i))) {
return o1.get(i) - o2.get(i);
}
}
return 0;
}
});
//去重复
for (int i = 1; i < tn.size(); i++) {
List<Integer> a = tn.get(i - 1);
List<Integer> l = tn.get(i);
if (a.get(0).equals(l.get(0))) {
if (a.containsAll(l) && l.containsAll(a)) {
tn.remove(i);
i--;
}
}
}
return tn;
}
------解决方案--------------------
public static void test4(int[] array, int begin, int num, int cVal, int val, List<Integer> result)
{
if (result.size()==num)
{
if (cVal==val)
{
System.out.println(result);
}
return;
}
for (int i = begin; i<array.length; i++)
{
if (cVal<val&&result.size()<num)
{
result.add(array[i]);
cVal += array[i];
test4(array,i+1, num, cVal, val, result);
cVal -= result.remove(result.size()-1);
}
}
}
public static void main(String[] args)
{
int[] array = { 1, 2, 3, 4 ,5,6,7,8,9};
test4(array, 0, 3, 0, 11, new ArrayList());
}