如何将圆形数组划分为k个连续元素组，以使最大和与最小和之间的差异最小.

本文介绍了如何将圆形数组划分为k个连续元素组，以使最大和与最小和之间的差异最小.的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

如何将圆形数组划分为k组连续元素，以使最大和与最小和之间的差异最小.每个组都有数组的连续元素. 例如，如果数组如下所示. [6 13 10 2]且k = 2则o/p应为18(6 + 10 + 2)-13 = 5.由于数组是圆形的6,10,2是数组的连续元素. 例如，如果数组如下所示. [6 13 2 10]并且k = 2，则o/p应该为16(6 + 10)-15(13 + 2)= 1.由于数组是圆形的6,10是数组的连续元素. 例如，如果数组如下所示. [100 92 133 201 34 34 34 94 108]，k = 4，然后按照以下步骤分组208(108,100)，225(92,133)，(201)，196(34、34、34、94)，所以225-196 = 29 我尝试过的事情: 以下是该问题的强力解决方案.我该如何优化呢?

How can I divide an circular array into k group of contiguous element such that difference between maximum sum and minimum sum is minimum. Each group have contiguous element of array. For e.g If the array is as follow. [6 13 10 2] and k=2 then o/p should be 18(6+10+2)-13=5. As array is circular 6,10,2 are contiguous element of array. For e.g If the array is as follow. [6 13 2 10] and k=2 then o/p should be 16(6+10)-15(13+2)=1. As array is circular 6,10 are contiguous element of array. For e.g If the array is as follow. [100 92 133 201 34 34 34 94 108] and k=4 then group as follow 208(108,100), 225(92,133), (201), 196(34,34,34,94) so 225-196=29 What I have tried: Following is the brute force solution for the question. How can I optimize this?

//#define MAX_POINT 6 #define ARR_SIZE 100 //#define K 4 #include <limits> #include<stdio.h> #include<iostream> using namespace std; int ai[]={6,13,2,10}; /* Utility function to print array arr[] */ void printArray(int arr[], int arr_size); int finddifference(int a[], int sizeai, int g){ int min = 16000; for(int i=0;i<sizeai;i++){ int j=0,k=i; int min_g=16000; int max_g=-16000; int sum=0; while(j<g){ int temp=a[j]; while(temp){ sum+=ai[k]; k=(k+1)%sizeai; temp--; } if(sum<min_g) min_g=sum; if(sum>max_g) max_g=sum; sum=0; j++; } if((max_g-min_g)<min) min=max_g-min_g; } return min; } /* The function prints all combinations of numbers 1, 2, ...MAX_POINT that sum up to n. i is used in recursion keep track of index in arr[] where next element is to be added. Initital value of i must be passed as 0 */ void printCompositions(int n, int i, int max_point, int g, int *min) { /* array must be static as we want to keep track of values stored in arr[] using current calls of printCompositions() in function call stack*/ static int arr[ARR_SIZE]; if (n == 0 && i==g) { int temp_min = finddifference(arr, max_point+g-1, g); *min = (temp_min<*min)?temp_min:*min; //printArray(arr,i); } else if(n > 0) { int k; for (k = 1; k <= max_point; k++) { arr[i]= k; printCompositions(n-k, i+1, max_point, g, min); } } } /* UTILITY FUNCTIONS */ /* Utility function to print array arr[] */ void printArray(int arr[], int arr_size) { int i; for (i = 0; i < arr_size; i++) printf("%d ", arr[i]); printf("\n"); } /* Driver function to test above functions */ int main() { int n, g; cin>>n; cin>>g; int max_point=n-g+1; int min = 16000; printCompositions(n, 0, max_point,g,&min); cout<<"Answer"<<min<<endl; getchar(); return 0; }

推荐答案

报价:

除此之外没有太多想法.

Not much idea beyond that.

由于您不知道任何智能算法可以解决此问题，因此答案是强力攻击.尽一切可能. 问题:每个"k"组的大小受到什么限制? 在"[6 13 2 10]和k = 2"中，每个组的大小为2，或者您可以拥有1和3?

Since you do not know any smart algorithm to solve this, the answer is brut force attack. Try every possibility. Question: What is the constraint on the size of each ''k'' groups ? in ''[6 13 2 10] and k=2'', each group is size 2 or you can have 1 and 3 ?

报价:

试图通过创建array和array的元素来解决数组中的元素之和，直到元素i.除此之外没什么主意.

Tried to solve by creating array and element of array are sum of elements of the array upto element i. Not much idea beyond that.

您在这里描述没有问题.您的数组模糊地与优化相关，而与问题解决无关. 第1步:设计一种有效的算法，想一想如何用纸和铅笔做事. 步骤2:一旦可行，请考虑优化. 要在这里获得真正的帮助，请返回您的代码和特定问题. 我们不做您的家庭作业. 家庭作业并非旨在测试您乞求他人完成工作的技能，而是可以让您思考并帮助您的老师检查您对所修课程的理解以及在应用这些课程时遇到的问题. 您的任何失败都会帮助您的老师发现您的弱点并采取补救措施. 您的任何失败都会帮助您学习什么有效，什么无效，这被称为试错"学习. 因此，请尝试一下，重新阅读您的课程并开始工作.如果您遇到特定问题，请显示代码并解释这个确切的问题，我们可能会提供帮助. 作为程序员，您的工作是创建解决特定问题的算法，您不能依靠别人永远为您完成任务，因此有时您必须学习如何.而且越早越好. 当您只是寻求解决方案时，这就像试图通过培训其他人来学习驾驶汽车. 创建算法基本上是在寻找数学并进行必要的调整以适合您的实际问题. 所谓发展"是指:系统地利用科学和技术知识来满足特定的目标或要求." BusinessDictionary [ ^ ] 那与拥有一个快速的Google并在找不到正确的代码的情况下放弃"是不一样的.

you describe no problem here. Your array is vaguely related to optimization, no to problem solving. Step 1: device an algorithm that work, think of how you do with a sheet of paper and a pencil. Step 2: once it works, think of optimizations. To get real help here, comeback with your code and specific problem. We do not do your HomeWork. HomeWork is not set to test your skills at begging other people to do your work, it is set to make you think and to help your teacher to check your understanding of the courses you have taken and also the problems you have at applying them. Any failure of you will help your teacher spot your weaknesses and set remedial actions. Any failure of you will help you to learn what works and what don''t, it is called ''trial and error'' learning. So, give it a try, reread your lessons and start working. If you are stuck on a specific problem, show your code and explain this exact problem, we might help. As programmer, your job is to create algorithms that solve specific problems and you can''t rely on someone else to eternally do it for you, so there is a time where you will have to learn how to. And the sooner, the better. When you just ask for the solution, it is like trying to learn to drive a car by having someone else training. Creating an algorithm is basically finding the maths and make necessary adaptation to fit your actual problem. The idea of "development" is as the word suggests: "The systematic use of scientific and technical knowledge to meet specific objectives or requirements." BusinessDictionary[^] That''s not the same thing as "have a quick google and give up if I can''t find exactly the right code".