|
精华帖 (0) :: 良好帖 (1) :: 新手帖 (3) :: 隐藏帖 (1)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-03-24
Excalibur 写道 ggzwtj 写道 楼主有用过背包算法，就是传说中的小偷想偷东西，但是包包的容量是有限的，拿那些东西才能取得最多的东西。
其实可以换个角度想问题，就可以把楼主的问题转换成背包问题了： 如果想让两个数组的和之差最小，这不就是让两个数组的和都非常接近总和的一半！当然很多情况下是不能是得两个数组的和相等，都等于总和的一半。 如果不想等的话，必然有一个数组的和是小于总和一半的。我们要做的就是怎么让这个小的部分最接近总和的一半。 所以，这个问题应该可以转化成0-1背包问题，而这个包的大小就是所有数总和的一半，最后我们要求的是用一定量的数字怎么把这个包装得最满。 所以，这不是一个NP问题。 ps：如果我对楼主的描述没有理解错的话。:) 这个公式我想不出来，尤其是要考虑包内个数必须为数组的长度 交换的意思应该是两个数组长度一致，1对1交换吧 是一对一交换，不过数组不一定等长吧， |
| 返回顶楼 | |
|
发表时间：2011-03-24
liuningbo 写道 是一对一交换，不过数组不一定等长吧， 对对，脑子坏了，呵呵 |
| 返回顶楼 | |
|
发表时间：2011-03-24
liuningbo 写道 看看写了个 ，实现不需数组长度一致，复杂度O(n^2),求好的算法
/** arr1={1,2,3};
* arr2={22,33,44,55};
* 交换两个矩阵数据
*/
public void exchange(){
int index=0;
int len=arr1.length;
int currMinus=getMinus();
while(true){
for (int i = 0; i < arr2.length; i++) {
echangeMatrix(index,i);//交换值
if(currMinus>getMinus()){
currMinus=getMinus();//一次循环中找到最小minus的
}else {
echangeMatrix(index,i);//若不是则不交换，即再换同一位置一次
}
}
index++;
if(index>=len){
break;
}
}
}
private void echangeMatrix(int index,int des){
int temp=0;
temp=arr1[index];
arr1[index]=arr2[des];
arr2[des]=temp;
}
/**计算和
* ryuuninbou
* @return int
*/
private int getMinus(){
int sum1=0;
int sum2=0;
for (int i = 0; i < arr1.length; i++) {
sum1+=arr1[i];
}
for (int i = 0; i < arr2.length; i++) {
sum2+=arr2[i];
}
return Math.abs(sum1-sum2);
} 我觉得你这个应该是n^3，当然如果优化一下求和过程，可以降得到n^2。 你能证明这个算法的正确性吗？ |
| 返回顶楼 | |
|
发表时间：2011-03-24
最后修改：2011-03-24
Excalibur 写道 我觉得你这个应该是n^3，当然如果优化一下求和过程，可以降得到n^2。
你能证明这个算法的正确性吗？
private int primalMinus=0;
private int sum1=0;
private int sum2=0;
private void primalMinus(){
for (int i = 0; i < arr1.length; i++) {
sum1+=arr1[i];
}
for (int i = 0; i < arr2.length; i++) {
sum2+=arr2[i];
}
primalMinus=Math.abs(sum1-sum2);
}
public void exchange(){
primalMinus();//计算最初差值
int index=0;
int len=arr1.length;
int currMinus=primalMinus;
while(true){
for (int i = 0; i < arr2.length; i++) {
echangeMatrix(index,i);//交换值
int afterChange=getMinus();
if(currMinus>=afterChange){
currMinus=afterChange;//一次循环中找到最小minus的
}else {
echangeMatrix(index,i);//若不是则不交换，即再换同一位置一次
}
}
index++;
if(index>=len){
break;
}
}
}
private void echangeMatrix(int index,int des){
int temp=0;
temp=arr1[index];
arr1[index]=arr2[des];
sum1+=arr1[index];
sum2-=arr1[index];
arr2[des]=temp;
sum1-=arr2[des];
sum2+=arr2[des];
primalMinus=Math.abs(sum1-sum2);
}
/**计算和
* ryuuninbou
* @return int
*/
private int getMinus(){
return primalMinus;
}
经过哥们提醒，改良了下，对于数组长度为m，n有m*n种交换数组，求其中差值最小的，结果应该是正确的 |
| 返回顶楼 | |
|
发表时间：2011-03-24
liuningbo 写道 Excalibur 写道 我觉得你这个应该是n^3，当然如果优化一下求和过程，可以降得到n^2。
你能证明这个算法的正确性吗？ 经过哥们提醒，改良了下，对于数组长度为m，n有m*n种交换数组，求其中差值最小的，结果应该是正确的 int[] arr1 = { 1, 2, 3, 4, 5, 100, 101 }; int[] arr2 = { 11, 12, 13, 14, 15,100, 170 }; 结果为 [100, 1, 2, 3, 4, 100, 101] 311 [5, 11, 12, 13, 14, 15, 170] 240 至少 [1, 2, 3, 4, 5, 100, 170] 285 [11, 12, 13, 14, 15, 100, 101] 266 比代码求出来的效果好 |
| 返回顶楼 | |
|
发表时间：2011-03-24
Excalibur 写道 liuningbo 写道 Excalibur 写道 我觉得你这个应该是n^3，当然如果优化一下求和过程，可以降得到n^2。
你能证明这个算法的正确性吗？ 经过哥们提醒，改良了下，对于数组长度为m，n有m*n种交换数组，求其中差值最小的，结果应该是正确的 int[] arr1 = { 1, 2, 3, 4, 5, 100, 101 }; int[] arr2 = { 11, 12, 13, 14, 15,100, 170 }; 结果为 [100, 1, 2, 3, 4, 100, 101] 311 [5, 11, 12, 13, 14, 15, 170] 240 至少 [1, 2, 3, 4, 5, 100, 170] 285 [11, 12, 13, 14, 15, 100, 101] 266 比代码求出来的效果好 还真是那么回事，兄弟知道哪里缺陷么？这样想到的解决办法就是合并排序再。。。 |
| 返回顶楼 | |
|
发表时间：2011-03-24
/*
有两个数组a,b，大小都为n,数组元素的值任意整形数，无序；
要求：通过交换a,b中的元素，使[数组a元素的和]与[数组b元素的和]之间的差最小。
*/
/*
求解思路：
当前数组a和数组b的和之差为
A = sum(a) - sum(b)
a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a[i] + b[j] - （sum(b) - b[j] + a[i])
= sum(a) - sum(b) - 2 (a[i] - b[j])
= A - 2 (a[i] - b[j])
设x = a[i] - b[j]
|A| - |A'| = |A| - |A-2x|
假设A > 0,
当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，x越接近A/2效果越好,
如果找不到在(0,A)之间的x，则当前的a和b就是答案。
所以算法大概如下：
在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。
*/
把算法大概实现了一下，程序如下：
1 int test(float a[], float b[], int n)
2 {
3 float sumA, sumB; //sumA为数组a总和，sumB为数组b总和
4 float sum_diff, num_diff; //sum_diff为a,b总和差， num_diff为a,b中各选的两个数之差
5 float temp1, temp2; //temp1为 每轮sum_diff/2， temp2为每轮所选两个数之差于temp1最接近的那个
6 int i, j;
7 float temp; //用于对调a,b间数
8 int tempi, tempj; //每轮所选两个数之差于temp1最接近的那组数
9 unsigned int flag_sum = 0, flag_num = 0; //flag_sum为1， sumA大于sumB; flag_num为1, 此轮存在两个数之差小于sum_diff
10
11
12
13
14 while(1){
15
16 //算出a,b数组和
17 sumA = 0;
18 sumB = 0;
19 for(i=0;i < n;i++)
20 {
21 sumA += a[i];
22 sumB += b[i];
23 }
24
25 if(sumA >= sumB){
26 sum_diff = sumA - sumB;
27 flag_sum = 1;
28 }
29 else
30 sum_diff = sumB - sumA;
31
32 temp1 = sum_diff/2;
33 temp2 = temp1;
34 tempi = 0;
35 tempj = 0;
36
37 //找出a,b间差值最接近sum_diff/2的那一对数
38 if(flag_sum == 1){ //sumA > sumB
39 for(i=0; i < n; i++)
40 for(j=0; j < n; j++)
41
42 if(a[i] > b[j]){
43 num_diff = a[i] - b[j];
44 if(num_diff < sum_diff){
45 flag_num =1;
46 if(num_diff >= temp1){
47 if(num_diff-temp1 < temp2){
48 temp2 = num_diff-temp1;
49 tempi = i;
50 tempj = j;
51 }
52 }
53 else{
54 if(temp1 - num_diff < temp2){
55 temp2 = temp1 - num_diff;
56 tempi = i;
57 tempj = j;
58 }
59 }
60 }
61 }
62 }
63 else{
64 for(i=0; i < n; i++)
65 for(j=0; j < n; j++)
66
67 if(a[i] < b[j]){
68 num_diff = b[j] - a[i];
69 if(num_diff < sum_diff){
70 flag_num =1;
71 if(num_diff >= temp1){
72 if(num_diff-temp1 < temp2){
73 temp2 = num_diff-temp1;
74 tempi = i;
75 tempj = j;
76 }
77 }
78 else{
79 if(temp1 - num_diff < temp2){
80 temp2 = temp1 - num_diff;
81 tempi = i;
82 tempj = j;
83 }
84 }
85 }
86 }
87 }
88
89 if(flag_num == 0)
90 break;
91
92 temp = a[tempi];
93 a[tempi] = b[tempj];
94 b[tempj] = temp;
95
96 flag_num = 0;
97 flag_sum = 0;
98 }
99
100 for(i=0; i < n;i++)
101 printf("%f\t",a[i]);
102
103 printf("\n");
104
105 for(i=0; i < n;i++)
106 printf("%f\t",b[i]);
107
108 printf("\n");
109
110 return 0;
111 }
112
113
114 int main(int argc, char *argv[])
115 {
116
117 float a[3] = {4,5,12};
118 float b[3] = {1,2,3};
119
120 test(a, b, 3);
121
122 return 0;
123 }
|
| 返回顶楼 | |
|
发表时间：2011-03-25
jigloo 写道 这是个NPC问题，所以就用穷举发了，在这里给出了一个用python的itertools的解法，个人认为比较简洁。
这个NPC有点滥用了吧，你知道他的含义吗 |
| 返回顶楼 | |
|
发表时间：2011-03-25
wjm251 写道 jigloo 写道 这是个NPC问题，所以就用穷举发了，在这里给出了一个用python的itertools的解法，个人认为比较简洁。
这个NPC有点滥用了吧，你知道他的含义吗 不是很清楚，期待你写个n*n*n或者n*n算法出来，注意:"数组里面的元素个数是相等的。" |
| 返回顶楼 | |
|
发表时间：2011-03-25
chinpom 写道
/*
有两个数组a,b，大小都为n,数组元素的值任意整形数，无序；
要求：通过交换a,b中的元素，使[数组a元素的和]与[数组b元素的和]之间的差最小。
*/
/*
求解思路：
当前数组a和数组b的和之差为
A = sum(a) - sum(b)
a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a[i] + b[j] - （sum(b) - b[j] + a[i])
= sum(a) - sum(b) - 2 (a[i] - b[j])
= A - 2 (a[i] - b[j])
设x = a[i] - b[j]
|A| - |A'| = |A| - |A-2x|
假设A > 0,
当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，x越接近A/2效果越好,
如果找不到在(0,A)之间的x，则当前的a和b就是答案。
所以算法大概如下：
在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。
*/
把算法大概实现了一下，程序如下：
1 int test(float a[], float b[], int n)
2 {
3 float sumA, sumB; //sumA为数组a总和，sumB为数组b总和
4 float sum_diff, num_diff; //sum_diff为a,b总和差， num_diff为a,b中各选的两个数之差
5 float temp1, temp2; //temp1为 每轮sum_diff/2， temp2为每轮所选两个数之差于temp1最接近的那个
6 int i, j;
7 float temp; //用于对调a,b间数
8 int tempi, tempj; //每轮所选两个数之差于temp1最接近的那组数
9 unsigned int flag_sum = 0, flag_num = 0; //flag_sum为1， sumA大于sumB; flag_num为1, 此轮存在两个数之差小于sum_diff
10
11
12
13
14 while(1){
15
16 //算出a,b数组和
17 sumA = 0;
18 sumB = 0;
19 for(i=0;i < n;i++)
20 {
21 sumA += a[i];
22 sumB += b[i];
23 }
24
25 if(sumA >= sumB){
26 sum_diff = sumA - sumB;
27 flag_sum = 1;
28 }
29 else
30 sum_diff = sumB - sumA;
31
32 temp1 = sum_diff/2;
33 temp2 = temp1;
34 tempi = 0;
35 tempj = 0;
36
37 //找出a,b间差值最接近sum_diff/2的那一对数
38 if(flag_sum == 1){ //sumA > sumB
39 for(i=0; i < n; i++)
40 for(j=0; j < n; j++)
41
42 if(a[i] > b[j]){
43 num_diff = a[i] - b[j];
44 if(num_diff < sum_diff){
45 flag_num =1;
46 if(num_diff >= temp1){
47 if(num_diff-temp1 < temp2){
48 temp2 = num_diff-temp1;
49 tempi = i;
50 tempj = j;
51 }
52 }
53 else{
54 if(temp1 - num_diff < temp2){
55 temp2 = temp1 - num_diff;
56 tempi = i;
57 tempj = j;
58 }
59 }
60 }
61 }
62 }
63 else{
64 for(i=0; i < n; i++)
65 for(j=0; j < n; j++)
66
67 if(a[i] < b[j]){
68 num_diff = b[j] - a[i];
69 if(num_diff < sum_diff){
70 flag_num =1;
71 if(num_diff >= temp1){
72 if(num_diff-temp1 < temp2){
73 temp2 = num_diff-temp1;
74 tempi = i;
75 tempj = j;
76 }
77 }
78 else{
79 if(temp1 - num_diff < temp2){
80 temp2 = temp1 - num_diff;
81 tempi = i;
82 tempj = j;
83 }
84 }
85 }
86 }
87 }
88
89 if(flag_num == 0)
90 break;
91
92 temp = a[tempi];
93 a[tempi] = b[tempj];
94 b[tempj] = temp;
95
96 flag_num = 0;
97 flag_sum = 0;
98 }
99
100 for(i=0; i < n;i++)
101 printf("%f\t",a[i]);
102
103 printf("\n");
104
105 for(i=0; i < n;i++)
106 printf("%f\t",b[i]);
107
108 printf("\n");
109
110 return 0;
111 }
112
113
114 int main(int argc, char *argv[])
115 {
116
117 float a[3] = {4,5,12};
118 float b[3] = {1,2,3};
119
120 test(a, b, 3);
121
122 return 0;
123 }
输入为： int[] arr1 = { 1, 2, 3, 4, 5, 6, 7, 239, 100}; 时出现死循环了吧
至少存在一个答案如下： int[] arr1 = { 21, 22, 23, 24, 25, 26, 27, 100,100};
这种贪心算法能证明可行吗？ 我觉得无法证明
|
| 返回顶楼 | |
在网上找了一篇帖子，给LZ参考一下：