从数组中取尽可能少的n个数，使其总和大等于指定值m
最近遇到一算法问题：
有一个int型数组，数组长度为l（l>0），数组里成员的值互不相等
现要从中取n个数（n的值要尽可能小），使其总和大等于指定值m（若无法等于m，则要求尽可能地接近）
public int[] getNewArray(int[] srcArray ,int m )
如：int[] srcArray={1,2,3}; m=6 返回 {3,3}
int[] srcArray={2,3}; m=1 返回 {2}
int[] srcArray={2,3,4}; m=9 返回{2,3,4}或{3,3,3}
望大伙多多帮忙，在此先谢过！！！
[解决办法]
看起来是子集和问题(SubSet Sum)的加强版,楼主可以看这个
http://blog.csdn.net/hhygcy/archive/2009/03/04/3955683.aspx
[解决办法]
先对数组arrInt排序(从大到小):
int temp = 0;
for (int k = arrInt.Length - 1; k > 0; k--)
{
for (int j = 0; j < arrInt.Length - 1; j++)
{
if (arrInt[j] < arrInt[j + 1])
{
temp = arrInt[j];
arrInt[j] = arrInt[j + 1];
arrInt[j + 1] = temp;
}
}
}
再
int sum = 0;
for(int i=0;i<arrInt.Length-1;i++)
{
sum += arrInt[i];
if (sum >= m)
{
MessageBox.Show(sum.ToString());
break;
}
}
[解决办法]
最普通的想法是可以用背包来解，求一个大小为M的背包，然后找出最接近的值Q，然后再求合为Q的最小子集。
不过感觉可以用贪心配合欧几里德扩展来解，效率会高一些。
[解决办法]
楼主这个基本就是个背包问题。
http://blog.csdn.net/topgun_topgun/archive/2007/06/20/1659988.aspx
[解决办法]
发一个JAVA版的实现。实际上没有想像的那么复杂，每一层只是找数组中的最大值就可以了，不用遍历整个数组。
如果有问题，请多多指教。
public class FindMax {
public void find(int[] fs, int m) {
if (fs == null || fs.length < 1) {
return;
}
int[] ft = new int[fs.length];
for (int i = 0; i < fs.length; i++) {
ft[i] = -1;
}
int s = 0;
int k = 0;
for ( int i = 0; i < ft.length; i++){
k = s;
for ( int j = 0; j < fs.length; j++){
if ( fs[j] + k == m){
ft[i] = fs[j];
output(ft);
return;
}else if(fs[j] + k < m){
if (fs[j] > ft[i]){
ft[i] = fs[j];
}
}else if (fs[j] + k > m){
continue;
}
}
s = s + ft[i];
}
output(ft);
}
/**
* @param args
*/
public static void main(String[] args) {
FindMax fm = new FindMax();
int[] fs = { 1, 2, 3, 6, 7 , 8 };
int t = 50;
fm.find(fs, t);
}
private void output(int[] fingles) {
StringBuffer s = new StringBuffer(fingles.length);
for (int j = 0; j < fingles.length; j++) {
if(fingles[j] == -1){
continue;
}
if (j != 0) {
s.append(",");
}
s.append(fingles[j]);
}
System.out.println(s.toString());
}
}
[解决办法]
比较复杂.
不是那么几行代码就能写出来的 得分好几个步骤才行
1.数组元素个数不定,
2.相加的元素个数不定,
3.而且还可以自相加,
4.前3种都无法找到等于目标值的元素时,还要找相近值的元素
按照以上的思路,分出几个步骤 用type[][]类型的2维数组存放所有可能值 然后就从这个2维数组里找出个数最少的一组，或者最接近的一组。
提示：
int[][] k
1个元素自相加的 放在 k[1]数祖里；
2个元素相加等于目标值的所有组合 放在k[2]里
3个。。。 放在k[3]里
模仿上面2维数组 同时还要存放不等于目标值的组合（找接近的答案用）
〉相加的元素个数不定 这个是关键
怎样得到所有的组合，且设计中间结果的数据结构 是解题的本质。
[解决办法]
public static int[] getNewArray(int[] srcArray, int m){int[] value = null;if (srcArray != null && srcArray.Length != 0 && m > 0){//这个地方要对srcArray排序int length = srcArray.Length, index = indexOf(srcArray, m, 0, length);if (index != length && m == srcArray[index]) value = new int[] { m };//找到一个相等的数else if (index == 0) value = new int[] { srcArray[0] };//如果可以返回0个元素的数组,这里要判断m与0接近还是与srcArray[0]接近else{//m大于最小的数int indexValue = srcArray[--index], count = m / indexValue, maxSub = m - indexValue * count;if (maxSub == 0){//找到一个约数value = new int[count];while ((--count) >= 0) value[count] = indexValue;}else{sumInfo sum, valueInfo = null;//0差值最佳组合Dictionary<int, sumInfo> minSum = new Dictionary<int, sumInfo>(), maxSum = new Dictionary<int, sumInfo>();//各种差值的偏小偏大最佳组合缓存sumInfo query = new sumInfo { indexs = new List<int>(), indexCount = new List<int>() };int lastQueryIndex = 0, querySub = maxSub, minCount = int.MaxValue, minSub;for (bool notNext, isFirst = true; lastQueryIndex >= 0; isFirst = false){if ((!isFirst) && query.indexs[lastQueryIndex] == 0){querySub += srcArray[query.indexs[lastQueryIndex]] * query.indexCount[lastQueryIndex];query.count -= query.indexCount[lastQueryIndex];query.indexs.RemoveAt(lastQueryIndex);query.indexCount.RemoveAt(lastQueryIndex);lastQueryIndex--;}if (isFirst || lastQueryIndex != -1){if (isFirst){query.indexs.Add(index);query.indexCount.Add(count);query.count = count;}else{querySub += srcArray[query.indexs[lastQueryIndex]];if (query.indexCount[lastQueryIndex] == 1){query.indexs[lastQueryIndex]--;query.indexCount[lastQueryIndex] = querySub / srcArray[query.indexs[lastQueryIndex]];}else{query.indexCount[lastQueryIndex]--;query.indexs.Add(query.indexs[lastQueryIndex] - 1);query.indexCount.Add(querySub / srcArray[query.indexs[++lastQueryIndex]]);}query.count += query.indexCount[lastQueryIndex] - 1;querySub -= query.indexCount[lastQueryIndex] * srcArray[query.indexs[lastQueryIndex]];}notNext = false;if (valueInfo == null || query.count < minCount){if (querySub == 0){//找到一个最佳组合minCount = query.count;valueInfo = copySumInfo(query);notNext = true;}else if (valueInfo == null || query.count < minCount - 1){index = (query.indexs[lastQueryIndex] == 0 ? 0 : indexOf(srcArray, querySub, 0, query.indexs[lastQueryIndex]));if (index != 0 && srcArray[index - 1] == querySub){//找到一个最佳组合valueInfo = copySumInfo(query);valueInfo.indexs.Add(index - 1);valueInfo.indexCount.Add(1);valueInfo.count = minCount = query.count + 1;notNext = true;}else{//测试偏大值if ((maxSub = srcArray[index] - querySub) < (minSub = querySub - (index == 0 ? 0 : srcArray[index - 1])) && ((!minSum.ContainsKey(maxSub)) || minSum[maxSub].count > query.count + 1) && ((!maxSum.ContainsKey(maxSub)) || maxSum[maxSub].count > query.count + 1)){sum = copySumInfo(query);sum.indexs.Add(index);sum.indexCount.Add(1);sum.count++;maxSum.Add(maxSub, sum);}//测试偏小值if ((!minSum.ContainsKey(minSub)) || minSum[minSub].count > query.count + 1){while (index != 0){query.indexs.Add(--index);query.indexCount.Add(count = querySub / srcArray[index]);query.count += count;querySub -= count * srcArray[index];lastQueryIndex++;if (notNext = (querySub == 0)){//找到一个最佳组合if (valueInfo == null || query.count < minCount){valueInfo = copySumInfo(query);minCount = query.count;}}else if ((!minSum.ContainsKey(querySub)) || minSum[querySub].count > query.count + 1){index = (querySub == 0 || index == 0 ? 0 : indexOf(srcArray, querySub, 0, index));}else notNext = true;if (notNext) break;}if ((!notNext) && ((!maxSum.ContainsKey(querySub)) || maxSum[querySub].count > query.count + 1)) minSum.Add(querySub, copySumInfo(query));}else notNext = true;}}else notNext = true;}if (notNext){//不可分解querySub += query.indexCount[lastQueryIndex] * srcArray[query.indexs[lastQueryIndex]];query.count -= query.indexCount[lastQueryIndex];query.indexs.RemoveAt(lastQueryIndex);query.indexCount.RemoveAt(lastQueryIndex);lastQueryIndex--;}}}//生成数组if (valueInfo == null){bool isMin = true;minSub = -1;foreach (int sub in minSum.Keys){if (minSub == -1 || sub < minSub) minSub = sub;}foreach (int sub in maxSum.Keys){if (minSub == -1 || sub < minSub){minSub = sub;isMin = false;}}valueInfo = (isMin ? minSum : maxSum)[minSub];}value = new int[valueInfo.count];for (index = 0, count = valueInfo.indexs.Count - 1; count >= 0; count--){for (minCount = valueInfo.indexCount[count]; minCount > 0; minCount--) value[index++] = srcArray[valueInfo.indexs[count]];}}}}return value;}
[解决办法]
第一步先试图接近
接近以后再试图优化，减小n
当然。。。我说的都是废话。。。
[解决办法]
1.先对数组A排序（倒序）
取A[i] i = 0 to count 做循环
2.A[i] 与 M 进行比较
1>.若M>A[i] 则 M = M - A[i] 将A[i]值放入到结果集中 再循环做第2步
2>.若M = A[i] M = M - A[i] 则将A[i]值放入到结果集中 结束循环
3>.若M < A[i] i++ 再循环做第2步
3.若M <> 0 则将 A[count-1] 放入到结果集中
代码就不写了，大概思路就是这样子，不知道我描述的清楚不？
[解决办法]
一番努力，应该可以实现了。确实是背包问题，只不过需要校验一下哪个是最优的解。代码如下：
public class FindMax {
List results = new ArrayList();
public void find(int[] fs, int m) {
if (fs == null || fs.length < 1) {
return;
}
int[] ft = new int[fs.length];
for (int i = 0; i < fs.length; i++) {
ft[i] = -1;
}
int c = 0;
int j = 0;
int[] cs = new int[fs.length];
for (int i = 0; i < ft.length; i++) {
ft[0] = fs[i];
c = 1;
j = 0;
while (c < fs.length + 1) {
//如果满足要求，后面的情况不用处理。
if (isValid(ft, c, m)){
j = fs.length;
}
if ( c == fs.length){
c--;
}
if (j == fs.length) {
if (c == 1) {
break;
}
c--;
j = cs[c];
} else {
ft[c] = fs[j];
cs[c] = j + 1;
c++;
if (c == fs.length) {
j = cs[c - 1];
} else {
j = 0;
}
}
}
}
}
private boolean isValid(int[] f, int c, int m){
boolean valid = true;;
for (int j = 0; j < c; j++) {
if (f[j] == -1) {
continue;
}
m -= f[j];
}
if ( m > 0){
valid = false;
}else{
m = Math.abs(m);
Result r = null;
for ( int i = results.size() - 1; i >= 0; i--){
r = (Result)results.get(i);
if ( m > r.no){
valid = false;
break;
} else if ( m < r.no){
results.remove(r);
valid = true;
continue;
} else if ( m == r.no){
if ( r.amount < c){
valid = false;
break;
}else if (r.amount > c){
results.remove(r);
valid = true;
continue;
}
}
if (isEqual(f, r.f, c)){
valid = false;
break;
}
}
if (valid){
r = new Result();
r.amount = c;
r.no = m;
r.f = new int[c];
for ( int j = 0; j < c; j++){
r.f[j] = f[j];
}
results.add(r);
}
}
return valid;
}
public void output(int[] fingles, int c ) {
StringBuffer s = new StringBuffer(fingles.length);
for (int j = 0; j < c; j++) {
if (fingles[j] == -1) {
continue;
}
if (j != 0) {
s.append(",");
}
s.append(fingles[j]);
}
System.out.println(s.toString());
}
public boolean isEqual(int[] s, int[] d, int c){
int[] temp = new int[c];
for ( int j = 0; j < c; j++){
temp[j] = d[j];
}
//查找是否相等
boolean equal = false;
for ( int j = 0; j < c; j++){
equal = false;
for ( int k = 0; k < temp.length; k++){
if(s[j] == temp[k]){
temp[k] = -1;
equal = true;
break;
}
}
if(!equal){
break;
}
}
return equal;
}
public class Result{
int amount;
int no = 0;
int[] f = null;
}
/**
* @param args
*/
public static void main(String[] args) {
FindMax fm = new FindMax();
int[] fs = { 1, 9, 7 };
int m = 13;
//int[] fs = { 1, 2, 3, 4 };
//int m = 3;
fm.find(fs, m);
FindMax.Result r = null;
for ( int i = 0; i < fm.results.size(); i++){
r = (FindMax.Result)fm.results.get(i);
fm.output(r.f, r.amount);
}
//int[] s = {3,5,5};
//int[] d = {5,5 ,3};
//
//System.out.println(fm.isEqual(s, d, 3));
}
}
[解决办法]
矩阵srcArray = [A1,A2……An]
矩阵valueArray=[V1,V2……Vn]
要求
int m ≧ srcArray*(valueArray的逆矩阵)
求解矩阵valueArray，并且要求得出矩阵valueArray里为0的值最多的那个？
不知道楼主是不是这个意思？
[解决办法]
$M=9;$arrInput=array(2,4,3);$arrResult=find_result($arrInput,$M);output($arrResult);//结果为：//n:3,s:9,data:4,3,2//n:3,s:9,data:3,3,3$M=20;$arrInput=array(11,2,3,5,7,8);$arrResult=find_result($arrInput,$M);output($arrResult);//n:3,s:20,data:11,7,2//n:3,s:20,data:8,7,5$M=40;$arrInput=array(7,9,23);$arrResult=find_result($arrInput,$M);output($arrResult);//n:3,s:41,data:23,9,9function find_result($arrInput,$M){ sort($arrInput); if($arrInput[0]<=0){ echo "重量必须大于0\n\n"; return; } $arrResult=array(); $s=0; $key=sizeof($arrInput); $arrData=array(); while($s<$M){ $arrData[]=$arrInput[$key-1]; $arrKey[]=$key; $s+=$arrInput[$key-1]; } $n=sizeof($arrData); $arrResult[]=array('n'=>$n,'s'=>$s,'arrData'=>$arrData); if($s==$M){ return ($arrResult); exit("Success"); } while(!key_is_zero($arrKey)){ $key=key_down($arrKey); if($key==0){ continue; } $s=key_weight($arrInput,$arrKey); while($s<$M){ $s+=$arrInput[$key-1]; key_fill($arrKey,$key); } $arrData=key_to_data($arrInput,$arrKey); $n=sizeof($arrData); $data=array('n'=>$n,'s'=>$s,'arrData'=>$arrData); key_result($arrResult,$data); //查看中间运行结果 //output($arrResult); } return $arrResult;}function key_result(&$arrResult,$data){ $result0=$arrResult[0]; if($result0['s']<$data['s']){//新结果重量大,舍弃 return; } if($result0['s']>$data['s']){//新结果重量小，原结果舍弃 $arrResult=array($data); return; } //两者重量相等，考虑n值 if($result0['n']<$data['n']){//新结果n大,舍弃 return; } if($result0['n']>$data['n']){//新结果n小，原结果舍弃 $arrResult=array($data); return; } //重量和n皆等，皆保留 $arrResult[]=$data; return;}function key_is_zero($arrKey){ if(sizeof($arrKey)==0 || $arrKey[0]==0){ return true; } return false;}function key_down(&$arrKey){ $n=sizeof($arrKey)-1; $key=$arrKey[$n]-1; unset($arrKey[$n]); return $key;}function key_to_data($arrInput,$arrKey){ $arrData=array(); foreach($arrKey as $key){ $arrData[]=$arrInput[$key-1]; } return $arrData;}function key_fill(&$arrKey,$key){ $n=sizeof($arrKey); $arrKey[$n]=$key;}function key_weight($arrInput,$arrKey){ $s=0; foreach($arrKey as $key){ $s+=$arrInput[$key-1]; } return $s;}function output($arrResult){ $arrOut=array(); foreach($arrResult as $result){ $strOut="n:".$result['n'].",s:".$result['s'].",data:".implode(',',$result['arrData']); $arrOut[]=$strOut; } echo implode("\n",$arrOut); echo "\n\n";}
------解决方案--------------------
我理解的题意：）
的解
1 好多人在买西瓜，我选了一个最大的85元，“决定就买这个了，一定买！必须买！”
2 从兜掏出50一打（一打表示要多少有多少），“大票，多给你钱我也买。”。 初使100--> 50 ＋ 50
3 先稳住老板，然后继续掏小票20一打， 更优，更新90--> 50 ＋ 20 + 20
4 然后继续掏小票12一打， 不优94--> 50 ＋ 20 ＋ 12 ＋ 12
保留--> 50 ＋ 20 + 20
5 然后继续掏小票5一打， 更优，更新85--> 50 ＋ 20 + 5 * 3（5张）
6 不用多给钱啦！
7 20*5 > 85 等一下，50的大票留着，不给老板；
8 重新从20开始掏钱……
20初使100--> 20 * 5
12更优，更新92--> 20 * 4 + 12
5更优，更新85--> 20 * 4 + 5（5张）
9 12*5 < 85 "老板，给你钱"
10 任选（50 ＋ 20 + 5 * 3）或者（20 * 4 + 5）
即a[] = {5, 12, 20, 50}时，和为85的解。
如果找不到和为85的情况，也没有问题，
如：没有5元的，就把当前的最优解返回：（50 ＋ 20 + 20）
[解决办法]
bool G( int D, const vector<int>& vec, vector<int>& vecResult )
{
for( int i = (int)vec.size() - 1; i >= 0; -- i )
{
int D2 = D - vec[i];
if( D2 < 0 )
continue;
vecResult.push_back( vec[i] );
if( D2 == 0 )
return true;
bool b = G( D2, vec, vecResult );
if( b )
{
return true;
}
else
{
vecResult.pop_back();
}
}
return false;
}
void main()
{
int arr[] = { 3, 7, 15, 23, 26, 35 };
vector<int> vec( arr, arr + sizeof( arr ) / sizeof( int ) );
int D = 139;
vector<int> vecResult;
while( ! G( D, vec, vecResult ) )
{
vecResult.clear();
++ D;
}
TRACE( "*** %d ***\n", D );
for( int i = 0; i < (int)vecResult.size(); ++ i )
{
TRACE( "%d\n", vecResult[i] );
}
}
输出：
*** 139 ***
35
35
35
15
7
3
3
3
3