从数组中找出最合适的组合 J#JavaScriptHTML

程序员文章站 2022-06-04 16:07:13

...

用js写的一个找最佳组合的代码。从一堆数字中找到和最接近指定数字的组合。没有用到递归，直接把所有的组合都找出来，然后从中找到最符合的组合显示出来。没有加注释，但肯定能用。

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
	<head>
		<title>找组合</title>
		<meta http-equiv="keywords" content="找组合">
		<meta http-equiv="description" content="从一堆数据中找出合适的组合">
		<meta http-equiv="content-type" content="text/html; charset=UTF-8">
	</head>
	<script type="text/javascript">
var IN,TARGET,TMP=new Array(64);
function sort(){
	for(var i=0;i<IN.length;i++){
		for(var j=IN.length-1;j>i;j--){
			if(IN[j-1]>IN[j]){
				var t=IN[j-1];
				IN[j-1]=IN[j];
				IN[j]=t;
			}
		}
	}
}
function loc(state){
	var size=0;
	for(var i=0;i<IN.length;i++){
		if((state&(1<<i))!=0){
			TMP[size++]=i;
		}
	}
	return TMP.slice(0,size);
}
function sum(loc){
	var ans=0;
	for(var i=0;i<loc.length;i++){
		ans+=IN[loc[i]];
	}
	return ans;
}
function main(){
	eval("IN=["+document.getElementById("IN").value+"];");
	eval("TARGET=["+document.getElementById("TARGET").value+"];");
	sort();
	var MAX=1<<IN.length,allans=new Array(0);
	for(var l=1;l<=MAX;l++){
		if(sum(loc(l))>=TARGET){
			allans.push(l);
		}
	}
	print(allans);
}
function line(loc){
	var sum=0,ans="";
	for(var i=0;i<loc.length;i++){
		sum+=IN[loc[i]];
		ans+=IN[loc[i]]+" +";
	}
	return ans.substr(0,ans.length-1)+"="+sum;
}
function print(state){
	var minSum=state[0];
	var minLen=state[0];
	for(var i=0;i<state.length;i++){
		var locl = loc(state[i]), locS = loc(minSum), locL = loc(minLen);
		var suml = sum(locl), sumS = sum(locS), sumL = sum(locL);
		if (suml < sumS || (suml == sumS && locl.length < locS.length)) {
			minSum = state[i];
		}
		if (locl.length < locL.length
				|| ((locl.length == locL.length && suml < sumL))) {
			minLen = state[i];
		}
	}
	var lineM = line(loc(minSum)), lineL = line(loc(minLen));
	document.getElementById("message").innerHTML="最短组合："+lineL+"</br>最近组合："+lineM;
}
	</script>
	<body>
		从<input type="text" id="IN" value="88,18,9,100,4.8,6.4,50,41.3,8.9,27.5,50" />
		里面	<input type="button" id="IN" value="去找" onclick="main();" />
		<input type="text" id="TARGET" value="287.76" /></br></br>
		<div id="message" />
	</body>
</html>