100分求个算法，语言不限 先到先得

Question

本帖最后由 T18LiQing 于 2013-04-02 13:28:13 编辑

Answer 1

接分了import java.util.ArrayList;
import java.util.List;/**
 * java 代码实现组合的算法 从n个数里取出m个数的组合是n*(n-1)*...*(n-m+1)/m*(m-1)*...2*1
 * 
 * @author dubensong
 * 
 */
public class AssemblyDemo {
/**
 * @param a:组合数组
 * @param m:生成组合长度
 * @return :所有可能的组合数组列表
 */
private List<int[]> combination(int[] a, int m) {
AssemblyDemo c = new AssemblyDemo();
List<int[]> list = new ArrayList<int[]>();
int n = a.length;
boolean end = false; // 是否是最后一种组合的标记
// 生成辅助数组。首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。
int[] tempNum = new int[n];
for (int i = 0; i < n; i++) {
if (i < m) {
tempNum[i] = 1; } else {
tempNum[i] = 0;
}
}
list.add(c.createResult(a, tempNum, m));// 打印第一种默认组合
int k = 0;// 标记位
while (!end) {
boolean findFirst = false;
boolean swap = false;
// 然后从左到右扫描数组元素值的"10"组合，找到第一个"10"组合后将其变为"01"
for (int i = 0; i < n; i++) {
int l = 0;
if (!findFirst && tempNum[i] == 1) {
k = i;
findFirst = true;
}
if (tempNum[i] == 1 && tempNum[i + 1] == 0) {
tempNum[i] = 0;
tempNum[i + 1] = 1;
swap = true;
for (l = 0; l < i - k; l++) { // 同时将其左边的所有"1"全部移动到数组的最左端。
tempNum[l] = tempNum[k + l];
}
for (l = i - k; l < i; l++) {
tempNum[l] = 0;
}
if (k == i && i + 1 == n - m) {// 假如第一个"1"刚刚移动到第n-m+1个位置,则终止整个寻找
end = true;
}
}
if (swap) {
break;
}
}
list.add(c.createResult(a, tempNum, m));// 添加下一种默认组合
}
return list;
} public int[] createResult(int[] a, int[] temp, int m) {
int[] result = new int[m];
int j = 0;
for (int i = 0; i < a.length; i++) {
if (temp[i] == 1) {
result[j] = a[i];
j++;
}
}
return result;
} public void print(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + "\t");
}
System.out.println();
} public void printResult(int[] a, int total) {
int sum = 0;
for (int i : a) {
sum += i;
}
if (sum == total) {
print(a);
}
for (int i = 0; i < a.length - 1; i++) {
List<int[]> list = combination(a, i + 1);
for (int[] arr : list) {
sum = 0;
for (int j : arr) {
sum += j;
}
if (sum == total) {
print(arr);
}
}
}
} public static void main(String[] args) {
AssemblyDemo c = new AssemblyDemo();
int[] a = { 1, 3, 4, 5, 8, 7, 8, 10, 34 };
c.printResult(a, 25);
}
}

Answer 2

import java.util.Arrays;public class Test {
public static void main(String[] args) {
int[] a = { 1,3,4,5,8,7,8,10,34};
for (int n = 1; n <= a.length; n++) {
int[] b = new int[n];
submit(a, 0, 0, n, b);
}
} public static void submit(int[] a, int c, int i, int n, int[] b) {
for (int j = c; j < a.length - (n - 1); j++) {
int sum = 0 ;
b[i] = a[j];
if (n == 1) {
//System.out.println();
for(int k=0;k<b.length;k++){
sum+= b[k];
}
if(sum==25){
System.out.println(Arrays.toString(b));
}
} else {
n--;
i++;
submit(a, j + 1, i, n, b);
n++;
i--;
}
}
}
}

Answer 3

package com.ccesun.bag;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class BagWork {

private int[] goods;

private int bagSize;

public BagWork(int[] goods, int bagSize){
this.goods = goods;
this.bagSize = bagSize;
}

public List<int[]> doWork(){
Boolean flags[] = new Boolean[goods.length];
Arrays.fill(flags, false);
int index = 0, bagSpace = bagSize, goodSize = goods.length;
List<int[]> result = new ArrayList<>();
int goodCount = 0;
while(index < goodSize){
while(index < goodSize){
if(bagSpace > goods[index]){
flags[index] = true;
bagSpace -= goods[index];
goodCount++;
}else if (bagSpace == goods[index]){
int[] scheme = new int[goodCount+1];
int tmp = goodCount;
flags[index] = true;
for(int i = index; i >= 0 && tmp >= 0; i--){
if(flags[i] == true){
scheme[tmp--] = i;
}
}
result.add(scheme);
flags[index] = false;
}
index++;
}
//回溯
if(goodCount == 0){
break;
}else{
for(int i = index -1; i >= 0; i--){
if(flags[i] == true){
bagSpace += goods[i];
goodCount--;
index = i + 1;
flags[i] = false;
if(index < goodSize){
break;
}
}
}
}
}
return result;
} /**
 * @param args
 */
public static void main(String[] args) {
int bagSize = 25, goods[] = new int[]{1, 3, 4, 5, 8, 7, 8, 10, 341, 3, 4, 5, 8, 7, 8, 10, 34};
BagWork bagWork = new BagWork(goods, bagSize);
List<int[]> result = bagWork.doWork();
StringBuilder sb = new StringBuilder();
for(int[] scheme : result){
for(int good : scheme){
sb.append(goods[good]).append(',');
}
sb.deleteCharAt(sb.length()-1);
System.out.println(sb.toString());
sb.delete(0, sb.length());
}
}}