求一算法
A数组和B数组包各含若干实数要求:
A和B数组中总共只能取出4个数字
A里面取出来的数相加后总合不能大于10(最后一个被加数加上后和大于10则按10算)
B里面取出来的数相加后总合不能大于10(最后一个被加数加上后和大于10则按10算)
A+B的和要尽可能的大
--------------------编程问答-------------------- A+B数组相加? --------------------编程问答-------------------- 学习中... --------------------编程问答-------------------- 有点没弄明白 --------------------编程问答-------------------- 有点 晕晕 --------------------编程问答-------------------- 麻烦先举个例子,把AB数组填一些数据进去,然后做个案例 --------------------编程问答-------------------- 额,俺的语文没学好,实在理解不了LZ字里行间的高深含义 --------------------编程问答-------------------- 我猜测lz的意思是不是这样的:
//前提条件
int alength_min = 5;//a数组的长度最小值
int alength_max = 10;//a数组的长度最大值
int blength_min = 5;//b数组的长度最小值
int blength_max = 10;//b数组的长度最大值
int avalue_min = 1;//a数组的值最小值
int avalue_max = 9;//a数组的值最大值
int bvalue_min = 1;//b数组的值最小值
int bvalue_max = 9;//b数组的值最大值
//初始化
int alength,blength;
System.Random r1 = new Random();
alength = r1.Next(alength_min, alength_max);
blength = r1.Next(blength_min, blength_max);
int[] A = new int[alength];
int[] B = new int[blength];
for(int i=0;i<alength;i++)
A[i] = r1.Next(avalue_min, avalue_max);
for(int i=0;i<blength;i++)
B[i] = r1.Next(bvalue_min, bvalue_max); --------------------编程问答-------------------- 不好意思,可能没表述清楚,重新描述下:
a[]={2,2,4,5,7,9}
b[]={3,4,2,4}
现在要在a[]和b[]中总共取出4个元素,使得他们的合尽可能的大,但是有些条件:
a[]/b[]中取出的元素相加的和不得大于10,如果大于10了,就按照10计算,
举个例子:
如a[]中取出9,7两个元素,9+7>10则a里面取出元素和算10,
由于a[]已经取出2个元素,b[]中还能取2个,取两个最大的4,4,则b中取出的元素和为4+4=8,所有元素和计为10+8=18;
但是这个不是最优的取法,正确的取法应该是a[]中取一个9,b[]中取4,4,3或2,这样a的和为9,b的和为10,总合就是9+10=19;
不知道这次表达清楚没...有些饶人.. --------------------编程问答-------------------- 用蛮力法可以做出来,可是用的时间比较多。。 --------------------编程问答-------------------- 两个序列各自排序
分别讨论0-4,1-3,2-2的分配方式,找出最大的 --------------------编程问答-------------------- 用贪心就可以,n*log(n) + m*log(m)的,对两个数组分别排序,从大到小算累加,以10为界限(以正数为界限),
a[]={2,2,4,5,7,9}
b[]={3,4,2,4}
=> A[] 2,2,4,5,7 And 9 (累加SumA = 9)
=> B[] 2,3 And 4,4 (累加SumB = 8)
取界限之后的部分合并为1个数组C
C[] 9 And 4,4排序后为9,4,4
如果需要选取的个数n<=3,则返回从C中选最大的n个数的和,如果个数n>=5 则返回20,如果n=4,则返回10 + max(SumA,SumB) --------------------编程问答--------------------
硬是没看明白...... --------------------编程问答-------------------- 看来我描述能力太弱了,给个简单的程序吧。
--------------------编程问答-------------------- 观望学习中。。。。 --------------------编程问答-------------------- 这。。。。 --------------------编程问答-------------------- 贪心法O(4n)就可以了,A与B组的初始预期价值都为10(组中任何大于组价值的数只能算做组价值),分别求出A与B的最大价值并取出最大价值,减少相关组的价值。循环直到取出4个数。如:
using System;
using System.Collections.Generic;
namespace CSharpTest
{
class Program
{
public static void Main()
{
int max = 10, selectCount = 5, result;
int[] a = new int[] { 2, 2, 4, 5, 7, 9 };
int[] b = new int[] { 3, 4, 2, 4 };
List<int> tList = new List<int>();
int sumA = Solve(a, max, tList);
int sumB = Solve(b, max, tList);
tList.Sort();
int[] c = tList.ToArray();
for (int i = c.Length - 2; i >= 0; i--)
c[i] += c[i + 1];
if (selectCount <= c.Length)
result = c[selectCount - 1];
else if (selectCount == c.Length + 1)
result = max + Math.Max(sumA, sumB);
else
result = max * 2;
Console.WriteLine("最大值为:{0}", result);
Console.ReadKey();
}
public static int Solve(int[] nums, int max, List<int> target)
{
int sum = 0;
Array.Sort(nums);
for (int i = nums.Length - 1; i >= 0; i--)
{
if (sum + nums[i] > max || nums[i] < 0)
break;
else
target.Add(nums[i]);
sum += nums[i];
}
return sum;
}
}
}
A[]={2,2,4,5,7,9}
B[]={3,4,2,4}
max[A]=10
max[B]=10
找到最大价值9并取出,并重置组价值
max[A]=10-9=1
max[B]=10
A[]={2,2,4,5,7}={1,1,1,1,1}
B[]={3,4,2,4}
找到最大价值4并取出,并重置组价值
max[A]=1
max[B]=10-4=6
A[]={2,2,4,5,7}={1,1,1,1,1}
B[]={3,4,2}
找到最大价值4并取出,并重置组价值
max[A]=1
max[B]=6-4=2
A[]={2,2,4,5,7}={1,1,1,1,1}
B[]={3,2}={2,2}
找到最大价值2(数3或2都可以)并取出,并重置组价值
max[A]=1
max[B]=2-2=0
A[]={2,2,4,5,7}={1,1,1,1,1}
B[]={3|2}={0} --------------------编程问答-------------------- 给个实际例子说说,这个要求实在想不出
补充:.NET技术 , C#