问一个算法的问题

0 0

问一个算法的问题10

现在给出10个数[a,b,c,d,e,f,g,h,i,j]
目的：把它们分成2组，每组相加后的和最接近

比如 acdeg:bfhij和分别为55和57 而 abcde:fghij和分别为43和77

那么acdeg:bfhij 就是我们要找的

我想了半天好像只能用穷举啊

问题补充：我给大家列一组数据【1,10,11,12,13,14,15,16,17,18】总和为【127】

一下是最接近的分组
【13,10,11,12,18】和为【64】以及【1,14,15,16,17】和为【63】
这样分组应该是两组之和最接近的了

问题补充：我的想法是：
先把所有的组合全部穷举出来，记录两分分组运算结果以及运算结果是由哪些数相加而来
然后将运算结果排序，这样就可以拿到想要的分组
我知道的算法不多，只知道这种情况应该要穷举

问题补充：可能是我没说明白
这个算法里面数据就是固定的10条，并且把它分成两组，每组5个数，两组和最接近

Java 算法动态规划

2013年10月22日 11:32

popopop
115
0 0 14

14个答案按时间排序按投票排序

0 0

采纳的答案

最终版
将约束条件增加
path.size()==5 即可

package ansj_test.ansj_test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 一个数组中倒找使得两个数组平均化的解
 * 
 * @author ansj
 * 
 */
public class java {
    // 需要计算的数组.ps已经排好序了
    private static int[] arr = new int[] { 1, 1, 2, 2, 3, 3, 4, 4, 5, 9999 };
    // 物品状态0,未放入背包.1放入
    private static int[] status = new int[arr.length];
    // 中位数
    private static int mid = 0;
    // 记录背包中的总数
    static int num = 0;

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Arrays.sort(arr);
        // 找到平均数
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        mid = sum / 2;

        // 构造一个集合使之小于等于mid,此时转化为背包问题
        for (int i = 0; i < arr.length; i++) {
            // 将array[i] 放入背包
            findMid(0, i, new ArrayList<Integer>());
        }

        // 一下代码就是为了打印结果可以忽略
        for (Integer index : maxPath) {
            status[index] = 1;
        }

        List<Integer> result1 = new ArrayList<Integer>();
        List<Integer> result2 = new ArrayList<Integer>();

        for (int i = 0; i < status.length; i++) {
            if (status[i] == 0) {
                result1.add(arr[i]);
            } else {
                result2.add(arr[i]);
            }
        }

        System.out.println("mid is " + mid);
        int sum1 = 0;
        for (Integer integer : result1) {
            sum1 += integer;
        }
        int sum2 = 0;
        for (Integer integer : result2) {
            sum2 += integer;
        }
        System.out.println(result1 + " = " + sum1);
        System.out.println(result2 + " = " + sum2);

    }

    private static int minMid = Integer.MAX_VALUE;
    private static List<Integer> maxPath;

    /**
     * 从i开始寻找一种组合使其最接近midmid
     * 
     * @param i
     */
    private static void findMid(int sum, int i, List<Integer> path) {
        // TODO Auto-generated method stub
        sum += arr[i];
        if (path.size() > 4) {
            return;
        }

        path.add(i);// 记录路径

        if (minMid == 0) { // 找到最优路径直接打印了
            return;
        } else if (path.size() == 5 && minMid > Math.abs(sum - mid)) {
            minMid = Math.abs(sum - mid);
            maxPath = path;
        }

        i++;
        for (int j = i; j < arr.length; j++) {
            findMid(sum, j, new ArrayList<Integer>(path));
        }
    }

}

2013年10月24日 11:22

ansjsun
129
0 1 5

5条评论

0 0

这次好了。。。。不好意思。。刚才糊涂了。。看来自己本身的思路还是不够开阔

package ansj_test.ansj_test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 一个数组中倒找使得两个数组平均化的解
 * 
 * @author ansj
 * 
 */
public class java {
    // 需要计算的数组.ps已经排好序了
    private static int[] arr = new int[] { 1, 1, 2, 2, 3, 3, 4, 4, 9999, 9999 };
    // 物品状态0,未放入背包.1放入
    private static int[] status = new int[arr.length];
    // 中位数
    private static int mid = 0;
    // 记录背包中的总数
    static int num = 0;

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Arrays.sort(arr);
        // 找到平均数
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        mid = sum / 2;

        // 构造一个集合使之小于等于mid,此时转化为背包问题
        for (int i = 0; i < arr.length; i++) {
            // 将array[i] 放入背包
            findMid(0, i, new ArrayList<Integer>());
        }

        // 一下代码就是为了打印结果可以忽略
        for (Integer index : maxPath) {
            status[index] = 1;
        }

        List<Integer> result1 = new ArrayList<Integer>();
        List<Integer> result2 = new ArrayList<Integer>();

        for (int i = 0; i < status.length; i++) {
            if (status[i] == 0) {
                result1.add(arr[i]);
            } else {
                result2.add(arr[i]);
            }
        }

        System.out.println("mid is " + mid);
        int sum1 = 0;
        for (Integer integer : result1) {
            sum1 += integer;
        }
        int sum2 = 0;
        for (Integer integer : result2) {
            sum2 += integer;
        }
        System.out.println(result1 + " = " + sum1);
        System.out.println(result2 + " = " + sum2);

    }

    private static int minMid = Integer.MAX_VALUE;
    private static List<Integer> maxPath;

    /**
     * 从i开始寻找一种组合使其最接近midmid
     * 
     * @param i
     */
    private static void findMid(int sum, int i, List<Integer> path) {
        // TODO Auto-generated method stub
        sum += arr[i];
        if (path.size() > 4) {
            return;
        }

        path.add(i);// 记录路径

        if (minMid == 0) { // 找到最优路径直接打印了
            return;
        } else if (minMid > Math.abs(sum-mid)) {
            minMid = Math.abs(sum-mid);
            maxPath = path;
        }

        i++;
        for (int j = i; j < arr.length; j++) {
            findMid(sum, j, new ArrayList<Integer>(path));
        }
    }

}

2013年10月24日 10:57

ansjsun
129
0 1 5

4条评论

0 0

好吧，楼主你赢了，如果真要各55分组的话，穷举问题也不大，C 10 5 = 252种情况吧，不多。如果一定要用什么算法，那么用我的方法，然后再把不是55分组的组合去掉，剩下的再比较(leftValue-rightValue)绝对值最接近0的那个情况就行了，呼应我之前的回答，我的结果包含了55分组的情况，而且还提供不止一种答案，不错吧~

2013年10月24日 10:36

QuarterLifeForJava
69
0 1 11

添加评论

0 0

保持5，5结构。

将结束条件改为

if (path.size()>4) {
			return;
		}

就可以

package ansj_test.ansj_test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 一个数组中倒找使得两个数组平均化的解
 * 
 * @author ansj
 * 
 */
public class java {
	// 需要计算的数组.ps已经排好序了
	private static int[] arr = new int[] {1,10,11,12,13,14,15,16,17,18 };
	// 物品状态0,未放入背包.1放入
	private static int[] status = new int[arr.length];
	// 中位数
	private static int mid = 0;
	// 记录背包中的总数
	static int num = 0;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Arrays.sort(arr);
		// 找到平均数
		int sum = 0;
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i];
		}
		mid = sum / 2;

		// 构造一个集合使之小于等于mid,此时转化为背包问题
		for (int i = 0; i < arr.length; i++) {
			// 将array[i] 放入背包
			findMid(0, i, new ArrayList<Integer>());
		}

		// 一下代码就是为了打印结果可以忽略
		for (Integer index : maxPath) {
			status[index] = 1;
		}

		List<Integer> result1 = new ArrayList<Integer>();
		List<Integer> result2 = new ArrayList<Integer>();

		for (int i = 0; i < status.length; i++) {
			if (status[i] == 0) {
				result1.add(arr[i]);
			} else {
				result2.add(arr[i]);
			}
		}

		System.out.println("mid is " + mid);
		int sum1 = 0;
		for (Integer integer : result1) {
			sum1 += integer;
		}
		int sum2 = 0;
		for (Integer integer : result2) {
			sum2 += integer;
		}
		System.out.println(result1 + " = " + sum1);
		System.out.println(result2 + " = " + sum2);

	}

	private static int maxMid = 0;
	private static List<Integer> maxPath;

	/**
	 * 从i开始寻找一种组合使其最接近midmid
	 * 
	 * @param i
	 */
	private static void findMid(int sum, int i, List<Integer> path) {
		// TODO Auto-generated method stub
		sum += arr[i];
		if (path.size()>4) {
			return;
		}

		path.add(i);// 记录路径

		if (maxMid == mid) { // 找到最优路径直接打印了
			return;
		} else if (maxMid < sum) {
			maxMid = sum;
			maxPath = path;
		}

		i++;
		for (int j = i; j < arr.length; j++) {
			findMid(sum, j, new ArrayList<Integer>(path));
		}
	}

}

2013年10月24日 10:34

ansjsun
129
0 1 5

3条评论

0 0

用了一个比较笨的方法

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 一个数组中倒找使得两个数组平均化的解
 * 
 * @author ansj
 * 
 */
public class java {
	// 需要计算的数组.ps已经排好序了
	private static int[] arr = new int[] {11,13,23,23,32,99 };
	// 物品状态0,未放入背包.1放入
	private static int[] status = new int[arr.length];
	// 中位数
	private static int mid = 0;
	// 记录背包中的总数
	static int num = 0;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Arrays.sort(arr);
		// 找到平均数
		int sum = 0;
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i];
		}
		mid = sum / 2;

		// 构造一个集合使之小于等于mid,此时转化为背包问题
		for (int i = 0; i < arr.length; i++) {
			// 将array[i] 放入背包
			findMid(0, i, new ArrayList<Integer>());
		}

		// 一下代码就是为了打印结果可以忽略
		for (Integer index : maxPath) {
			status[index] = 1;
		}

		List<Integer> result1 = new ArrayList<Integer>();
		List<Integer> result2 = new ArrayList<Integer>();

		for (int i = 0; i < status.length; i++) {
			if (status[i] == 0) {
				result1.add(arr[i]);
			} else {
				result2.add(arr[i]);
			}
		}

		System.out.println("mid is " + mid);
		int sum1 = 0;
		for (Integer integer : result1) {
			sum1 += integer;
		}
		int sum2 = 0;
		for (Integer integer : result2) {
			sum2 += integer;
		}
		System.out.println(result1 + " = " + sum1);
		System.out.println(result2 + " = " + sum2);

	}

	private static int maxMid = 0;
	private static List<Integer> maxPath;

	/**
	 * 从i开始寻找一种组合使其最接近midmid
	 * 
	 * @param i
	 */
	private static void findMid(int sum, int i, List<Integer> path) {
		// TODO Auto-generated method stub
		sum += arr[i];
		if (sum > mid) {
			return;
		}

		path.add(i);// 记录路径

		if (maxMid == mid) { // 找到最优路径直接打印了
			return;
		} else if (maxMid < sum) {
			maxMid = sum;
			maxPath = path;
		}

		i++;
		for (int j = i; j < arr.length; j++) {
			findMid(sum, j, new ArrayList<Integer>(path));
		}
	}

}

2013年10月23日 22:59

ansjsun
129
0 1 5

2条评论

0 0

这个就是Partition problem,是NP-完全问题，但存在一个伪多项式动态规划算法，时间复杂度是O(Nn),N是所有输入数字的和，n是数字的个数。详见：http://en.wikipedia.org/wiki/Partition_problem

2013年10月23日 16:58

OpenMind
704
0 1 13

添加评论

0 0

晚上没事干自己写了写。应该是这个意思。没找到特殊情况。如果你找到了告诉我我在修改

mport java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
/**
 * 一个数组中倒找使得两个数组平均化的解
 * @author ansj
 *
 */
public class java {
	// 需要计算的数组.ps已经排好序了
	private static int[] arr = new int[] { 1, 3, 10, 20, 32, 321, 132, 31, 3, 123, 123, 12, 31, 31, 31, 231, 23, 123, 12, 321, 312, 23, 123 };
	// 物品状态0,未放入背包.1放入
	private static int[] status = new int[arr.length];
	// 中位数
	private static int mid = 0;
	// 记录背包中的总数
	static int num = 0;
 
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Arrays.sort(arr);
		// 找到平均数
		int sum = 0;
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i];
		}
		mid = sum / 2;
 
		// 构造一个集合使之小于等于mid,此时转化为背包问题
		for (int i = 0; i < arr.length; i++) {
			// 将array[i] 放入背包
			if (addInPackage(i)) {
				break;
			}
		}
 
		
		//一下代码就是为了打印结果可以忽略
		List<Integer> result1 = new ArrayList<Integer>();
		List<Integer> result2 = new ArrayList<Integer>();
 
		for (int i = 0; i < status.length; i++) {
			if (status[i] == 0) {
				result1.add(arr[i]);
			} else {
				result2.add(arr[i]);
			}
		}
 
		System.out.println("mid is " + mid);
		int sum1 = 0;
		for (Integer integer : result1) {
			sum1 += integer;
		}
		int sum2 = 0;
		for (Integer integer : result2) {
			sum2 += integer;
		}
		System.out.println(result1 + " = " + sum1);
		System.out.println(result2 + " = " + sum2);
 
	}
 
	private static boolean addInPackage(int i) {
		// TODO Auto-generated method stub
		num += arr[i];
		status[i] = 1;
 
		if (num == mid) {// 等于中位数找到最优解直接跳出了哦
			return true;
		} else if (num < mid) {// 小于中位数背包还能放
			return false;
		} else { // 超过背包容量,需要选择性弹出
			int maxJ = 0;
			for (int j = 0; j < status.length; j++) {// 尝试由小到大弹出
				if (status[j] == 0) {// 说明没放入背包那么不考虑
					continue;
				}
				// 如果弹出后满足条件.那么就弹出
				if (num - arr[j] == mid) {
					pop(j);
					return true;
				} else if (num - arr[j] < mid) {
					// 弹出j
					pop(j);
					return false;
				}
				maxJ = j;
			}
			// 如果一路没有解那么弹出最大结束,弹出maxJ
			pop(maxJ);
			return true;
		}
	}
 
	//弹出操作
	private static void pop(int j) {
		// TODO Auto-generated method stub
		num -= arr[j];
		status[j] = 0;
	}
}

2013年10月23日 14:53

ansjsun
129
0 1 5

5条评论

0 0

我看了下你的补充，对于个别数与其他数相距很大的情况下我的方法不适用，那么如何改进呢？很简单，只需将排序算法去除，对于list多进行几次collectins.shuffes(list),然后判断(leftValue-rightValue)绝对值最接近0的那个情况就行了，而且这样一来，可以解出多种答案来。

2013年10月23日 06:50

QuarterLifeForJava
69
0 1 11

添加评论

0 0

我只能说.这个是背包问题...动态优化来解决的.貌似不是很容易...

2013年10月22日 21:45

ansjsun
129
0 1 5

添加评论

0 0

楼主不好意思。。来晚了，想了下，再仔细看了你的题目，之前好像把你题目的意思理解错了，看下这个答案如何：

package test;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author QuarterLiftForJava
 * @version V0.1
 * 只是一种方法一种答案组合
 */
public class Test {
	
	//假设数值范围为1-10
	private static final int number = 10;
	
	private static List<Integer> list  = new ArrayList<Integer>();
	
	private static List<Integer> leftList  = new ArrayList<Integer>();
	
	private static List<Integer> rightList  = new ArrayList<Integer>();
	
	private static int leftValue = 0;
	
	private static int rightValue = 0;

	public static void main(String[] args) {
		//随机生成1-10之间的十个数
		int arry[] = new int[10];
		for(int i=0;i<10;i++){
			arry[i] = new Random().nextInt(number)+1;
		}
		sort(arry);
		System.out.println(list);
		while(list.size()!=0){
			balance(leftValue,rightValue);
		}
		System.out.println(leftList);
		System.out.println(rightList);
	}
	
	public static void balance(int left,int right){
		int x = list.remove(0);
		if(x+left>x+right){
			rightList.add(x);
			rightValue = rightValue+x;
		}else{
			leftList.add(x);
			leftValue = leftValue+x;
		}
	}

	public static void sort(int[] arry){
		for (int i = 0; i < arry.length; i++) {
			for (int j = 0; j < i; j++) {
				if(arry[i]>arry[j]){
					arry[i] = arry[i]^arry[j];
					arry[j] = arry[i]^arry[j];
					arry[i] = arry[i]^arry[j];
				}
			}
		}
		for (int i = 0; i < arry.length; i++) {
			list.add(arry[i]);
		}
	}
}

2013年10月22日 21:29

QuarterLifeForJava
69
0 1 11

添加评论

0 0

我想的是先排序，然后从大到小开始分组。加上楼上代码的想法写了下面代码，楼主看看是不是你想要的。

package com.sx.test;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 * @author  ul
 */
public class TestNum{
	
	//假设数值范围为1-100
	private static final int number = 100;
	private static int before = 0;
	private static int after = 0;
	
	public static void main(String[] args) {
		List<Integer> list = new ArrayList<Integer>();
		int arry[] = new int[10];
		for(int i=0;i<arry.length;i++){
			arry[i] = new Random().nextInt(number)+1;
			list.add(arry[i]);
			System.out.print(arry[i]+" ");
		}
		System.out.println();
		Collections.sort(list);
		
		List<Integer> be = new ArrayList();
		List<Integer> af = new ArrayList();
		
		Integer array[] = list.toArray(new Integer[]{});
		for(int i = 9;i>=0;i--){
			if(before>after){
				after+= array[i];
				af.add(array[i]);
			}else{
				before+=array[i];
				be.add(array[i]);
			}
		}
		System.out.println("前部分："+be+"和："+getsum(be));
		System.out.println("后部分："+af+"和："+getsum(af));
	}
	
	public static int getsum(List<Integer> a){
		int sum = 0;
		for(Integer i : a){
			sum += i;
		}
		return sum;
	}
}

2013年10月22日 17:48

ueu2715
15
0 0 6

1条评论

0 0

不好意思，上班时间，不敢多想。。。好像还是不大对，你再看看吧，回去给你好好想想，更正下。

for(int i=0;i<arry.length/2;i++){
			/**初始化*/
			before += arry[beforecount];
			after  += arry[aftercount];
			/**初始化*/
			if((before==after)||(i>=arry.length/2)){
				break;
			}else if(before<=after){
				before += arry[beforecount++];
			}else if(before>=after){
				after  += arry[aftercount--];
			}
			finalResult = i;
		}

2013年10月22日 16:24

QuarterLifeForJava
69
0 1 11

添加评论

0 0

看下是不是你想要的，如果我对你的要求理解错了，请再和我说下，我再编程，代码如下：

package test;

import java.util.Random;

/**
 * @author  QuarterLifeForJava
 * @version V0.1
 */
public class Test{
	
	//假设数值范围为1-10
	private static final int number = 10;
	private static int beforecount = 0;
	private static int aftercount = 10-1;
	private static int before = 0;
	private static int after = 0;
	private static int finalResult = 0;
	
	public static void main(String[] args) {
		int arry[] = new int[10];
		for(int i=0;i<arry.length;i++){
			arry[i] = new Random().nextInt(number)+1;
			System.out.print(arry[i]+" ");
		}
		System.out.println();
		for(int i=0;i<arry.length/2;i++){
			/**初始化*/
			before += arry[beforecount++];
			after  += arry[aftercount--];
			/**初始化*/
			if((before==after)&&(i>=arry.length/2)){
				break;
			}else if(before<after){
				before += arry[beforecount++];
			}else if(before>after){
				after  += arry[aftercount--];
			}
			finalResult = i;
		}
		System.out.println("前部数组");
		for(int i=0;i<finalResult;i++){
			System.out.print(arry[i]+" ");
		}
		System.out.println();
		System.out.println("后部数组");
		for(int i=finalResult;i<arry.length;i++){
			System.out.print(arry[i]+" ");
		}
	}
}

2013年10月22日 16:15

QuarterLifeForJava
69
0 1 11

1条评论

0 0

先排好序之后再从头穷举分组。
合的差异应该是从大到小过了临界值之后会再变大。
取得该临界值就是结果。

运气好的话是能减少一半左右的循环量的（最差情况是最后一个数是一组，前面所有是一组）。
不过多了一次排序。

2013年10月22日 13:27

red008
217
0 1 24

1条评论

相关推荐

前端校招常问算法.docx: 前端校招常问算法本文档主要收集了前端校招中常见的算法问题，涵盖字符串、数组、链表、树、栈、队列等多个领域。通过本文档，可以快速了解常见的算法问题，并掌握解题思路和方法。一、字符串算法 1. 字符串...

汽车加油问题+算法设计: 在本文中，我们将深入探讨如何解决“汽车加油问题”并设计一个有效的算法。这是一个典型的路径优化问题，可以利用贪心算法来求解。首先，我们要理解问题的核心：找到一种策略，使得汽车在行驶过程中加油次数最少，...

车辆路径matlab代码优化问题解决:遗传算法，蚁群算法，禁忌搜索算法，模拟退火算法: 要求每个工人只做一项工作，每项工作只由一个工人完成。怎样指派工人完成工作可以使所用总时间最少？ tabu 禁忌搜索算法解决解决商旅问题问题描述：某5个城市旅行商问题，用禁忌搜索算法实使得旅行商走过所有...

回溯算法求解八皇后问题: 八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线...

蚁群算法解决TSP问题（31城）matlab: 这个问题是著名的NP-hard问题，没有已知的多项式时间解决方案，因此通常采用启发式算法来寻找近似解。【MATLAB】是MathWorks公司开发的一种矩阵编程语言，广泛应用于数值计算、图像处理、数据分析等领域。在本案例...

面试中经常会碰到的算法问题: 这个问题通常用递归策略解决，通过将大问题拆解为小问题来实现。接着，二叉树遍历是数据结构和算法中的重要概念，包括前序遍历、中序遍历和后序遍历。前序遍历顺序为根-左-右，中序遍历为左-根-右，后序遍历为左-...

粒子群优化算法源码实例（matlab）.rar: 多个函数利用多种粒子群算法解决优化问题：用二阶粒子群优化算法求解无约束优化问题用二阶振荡粒子群优化算法求解无约束优化问题用混沌粒子群优化算法求解无约束优化问题用基于选择的粒子群优化算法求解无约束优化问...

贪心算法——最少硬币找钱: 这个问题不仅关乎日常生活中的便利性，也是计算机科学领域内一个有趣且实用的研究课题。在本篇文章中，我们将探讨如何利用贪心算法来解决这一问题。 **问题描述**：假设有一组硬币，每种硬币的面值均为正整数。现在...

面试中经常被问到的80道算法题: 这个问题考察了我们对二元查找树的理解和对指针操作的掌握。知识点二: 设计包含 min 函数的栈在这道题中，我们需要设计一个栈结构，使得它能够在 O(1) 的时间复杂度下实现 min 函数。为了实现这一目标，我们需要...

改进的遗传算法求解tsp: TSP（Traveling Salesman Problem，旅行商问题）是计算机科学与运筹学领域中的一个重要问题，它涉及寻找一条穿越所有指定地点恰好一次，并最终返回出发点的最短路径。随着地点数量的增加，TSP问题的解决方案数量呈...

算法设计装载问题: 有一批集装箱要装上载重量为c的轮船。其中集装箱i的重量为wi，现最优载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。编程任务：对于给定的n个集装箱和轮船的载重量c,编程计算装入的最优...

算法设计与分析（用分治法求解棋盘覆盖问题）: 这个问题的一个直观解决方案是寻找一种放置方式，使得棋盘上的每个单元格都被至少一个皇后覆盖，且任意两个皇后之间不存在攻击关系。 **分治法** 是一种重要的算法设计策略，其基本思想是将大问题分解为若干个规模...

【VRP问题】基于禁忌搜索算法求解带时间窗车辆路径规划问题（VRPTW）惩罚函数版matlab源码.zip: 在这个问题中，禁忌搜索算法（Tabu Search）是一种高效的全局优化方法，用于寻找接近全局最优解的解决方案。它通过维护一个短期记忆结构——禁忌列表，来避免早熟收敛，即在搜索过程中禁止近期已经访问过的解再次被...

JAVA算法编程题目及答案.doc: 该题目要求学习者编写一个JAVA程序来解决古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？该题目旨在考察学习者...

算法分析汽车加油问题: 设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。对于给定的n和k(k )个加油站位置，编程计算最少加油次数。 Input 有多个测试用例。每个测试用例输入数据的第一行有2 个正整数n和k，表示...

MATLAB遗传算法解决旅行商问题（TSP）、多旅行商问题（MTSP）及其变体（共计39种情况）: 遗传算法在此问题上的应用，首先需要定义一个编码方案，如使用整数编码表示城市顺序，然后设置适应度函数为路径的总距离。通过轮盘赌选择、单点交叉和随机变异操作，逐步改进解的空间探索。 2. **多旅行商问题...

百鸡问题算法设计与分析: ### 百鸡问题算法设计与分析 #### 一、问题背景及定义 “百鸡问题”是一道经典的数学问题，出自中国古代数学名著《算经》，原问题表述为：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、...

JAVA经典算法面试39题及答案: 答案：使用循环语句和条件语句可以解决该问题，判断素数的方法是：用一个数分别去除 2 到 sqrt(这个数)，如果能被整除，则表明此数不是素数，反之是素数。程序 3：水仙花数题目：打印出所有的“水仙花数”，所谓...

动态规划教程动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解求得原问题的解。与分治法不同的是，适合于动态规划法求解的问题，经分解求得的子问题往往不是互相独立的。若用分治法来解决这类问题，则分解得到的子问题的数目太多，以至于最后解决原问题需要耗费指数时间。然而，不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果我们能够保存解决的子问题的答案，而在需要时再找出已求得的答案，这样就可避免大量重复计算，从而得: 例如，多段图问题是一个典型的动态规划应用场景。多段图是由多个不相交的子图组成，每个子图代表一段，源结点s和汇点t是唯一节点。动态规划可以用来找到从s到t的最短路径，通过定义状态（如节点到达某点的最短距离）...