问题:
给定n个正整数wi和一个正整数m,在这n个正整数中找出一个子集,使得子集中的正整数之和等于m。
解的形式:
设定一个n元组(x0,x1,...xn-1),如果wi包含在这个子集中,xi就等于1,反之等于0.
BoundFunction:
算法伪代码:
/**
*
*/
package com.iteye.caoruntao.sumofsub;
/**
* @author caoruntao
*
*/
public class SumOfSub {
private int w[];
private int m;
private int x[];
public SumOfSub(int w[], int m, int n){
this.w = w;
this.m = m;
this.x = new int[n];
}
public void computeSumOfSub(int s, int k, int r){
x[k] = 1;
if(s+w[k] == m){
printResult(k);
System.out.println("*************");
}
else if(s+w[k]+w[k+1] <= m){
computeSumOfSub(s+w[k],k+1,r-w[k]);
}
if(s+r-w[k]>=m && s+w[k+1]<= m){
x[k] = 0;
computeSumOfSub(s, k+1, r-w[k]);
}
}
public void printResult(int k){
for(int i=0; i<=k; i++){
if(x[i] == 1){
System.out.println(i+1);
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int w[] = new int[]{7,11,13,24};
SumOfSub sumOfSub = new SumOfSub(w,31,4);
int r = 0;
for(int i=0; i<4; i++){
r += w[i];
}
sumOfSub.computeSumOfSub(0, 0, r);
}
}
- 大小: 6.9 KB
- 大小: 35.8 KB
分享到:
相关推荐
用回溯法实现子集和问题的完整代码
试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数,并将此函数用于解0-1背包问题。 0-1 背包问题描述如下:给定n 种物品和一个背包。物品i的重量是wi,其价值为...
试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数,并将此函数用于解装载问题。 装载问题描述如下:有一批共n个集装箱要装上艘载重量为c的轮船,其中集装箱i的...
利用回溯法求子集和(给定sum,求出任意一个满足条件的集合)
试设计一个解子集和问题的回溯法。对于给定的正整数的集合 S={x1,x2,…,xn }S={x1,x2,…,xn }和正整数 c,编程计算 S 的一个子集S1,使得∑x∈S1x=c ∑x∈S1x=c。数据输入:第 1 行有 2 个正整数 n 和 c,n ...
试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数,并将此函数用于解装载问题。 装载问题描述如下:有一批共n个集装箱要装上艘载重量为c的轮船,其中集装箱i的...
给定N个数,和一个整数M,判定是否可以从N个数中取出若干个数,使它们的和等于M。输出:YES或者NO。把N个数看成一个集合,问题就是从这个集合中选出一个子集,使这个子集满足和是M
本代码大量注释,便于理解。回溯法解决01背包问题,相对于动态规划来说,我们首先得了解问题的解空间,了解解空间的组织结构,最后搜索解空间,其中加入约束条件和限界条件是关键,否则就是穷举了。
试设计一个解子集和问题的回溯法。 «编程任务: 对于给定的正整数的集合S={x1,x2,...,xn}和正整数c,编程计算S 的一个子集 S1,使得x∈S1,∑x=c. Input 由文件input.txt 提供输入数据。文件第1 行有2 个正整数...
试设计一个解子集和问题的回溯法。 算法设计:对于给定的正整数的集合S={x1,x2,...,xn}和正整数c,计算S的一个子集S1,使得子集里的元素之和为c。 数据输入:由文件input.txt提供输入数据。文件第1行有2个正整数n和c...
试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数,并将此函数用于解0-1背包问题。 0-1 背包问题描述如下:给定n 种物品和一个背包。物品i的重量是wi,其价值为...
试设计一个解子集和问题的回溯法。 编程任务: 对于给定的正整数的集合S={ 1 x , 2 x ,…, n x }和正整数c,编程计算S 的一个子集S1,使得。 数据输入: 第1 行有2 个正整数n 和c,n 表示S 的大小,c是...
子集和数问题,回溯法实现
本例采用了java编写的图的m着色问题,采用的回溯法,参考:算法设计与分析
回溯法求子集:输入n,输出集合{1,2,…,n}的所有子集(n) 回溯法求子集:输入n,输出集合{1,2,…,n}的所有子集(n)
题目分析:数组长度为n的数组的所有子集,其长度从0(空数组)到n(原数组)不等,因此我们可以使用回溯法来探寻不同长度子数组的所有可能性。 由于回溯法刚开始的时候理解起来有难度,所以我们首先来结合代码进行...
ACM中的回溯法:搜索是人工智能中的一种基本方法,也是信息学竞赛选手所必须熟练掌握的一种方法。我们在建立一个搜索算法的时候,首要的问题不外乎两个: 1. 建立算法结构。 2. 选择适当的数据结构。 然而众所周知的...
回溯法实现n皇后问题,并输出每种放法的皇后位置
回溯法的基本思想、回溯法的递归流程、用回溯法解决问题 的步骤;注意概念:解空间、可行解、约束函数、限界函数。 子集树和排列树的搜索; 皇后问题的回溯算法 * ; Hamilton 回路 * 与旅行商问题的回溯...
很多人在算法分析中说打印子集很难 我当初用c编写的一个程序,是利用文件的打开,复制存取中间子集来实现了打印所有的子集