7

我在编码比赛中遇到了这个问题-

您将获得一个正整数数组，并且可以在需要时更改任何整数的符号。编写一个程序来计算这个数组的最小和。这个总和应该 >= 0。例如：Array = {1,2,4,5} 然后 sum = 0 因为我们改变 1 和 5 {-1,2,4,-5} 的符号

我对这个问题的解决方案是对数组进行排序并找到所有成员的总和。然后我会从最大数开始迭代地从总和减少 2*（排序数组值） - 直到总和变为 0 或直到它变为负数。

但我的解决方案是错误的。取 12、13、14、15、16、50。我的代码将 50 更改为 -50 并停止（即 min sum = 20）。但答案应该是 12,-13,-14,-15,-16,50（最小总和 = 4）

4

4 回答 4

9

这个问题可以改成背包问题

考虑这个问题：

给你 n 个整数，显然，你可以计算这些数字的总和，假设它是 S

您现在需要从中选择一组数字，并旨在将这些选择的数字相加以尽可能接近 S/2

这可以使用与背包问题非常相似的 DP 算法来完成

你现在能做到吗？:)

这篇文章只是一个提示，如果您需要更多帮助，我可以提供更多详细信息

于 2013-01-11T08:06:14.747 回答
4

我被其他答案激怒了，说了一些关于背包的事情。

Knap-Sack 意味着您有一个目标和S一个权重列表，A并且您正在寻找总和为.AS

对我来说，它看起来更像是制造期调度，您有两台机器并且必须将所有作业分配给它们，以使制造期最小化。

因此，您可以将其视为两个堆栈，并尝试将它们的高度差异最小化。

3/2 近似算法是这样的：

  • 对列表进行排序（最大到最小）
  • 对于每个对象，将其放在具有最低高度的堆栈上

您可以通过将较小堆栈上的所有对象的符号变为负数来获得近似值。（即计算两个堆栈的绝对差）

如果您搜索最小制造时间调度，您可以找到一个PTAS和一个需要在列表长度中指数时间的精确算法。

于 2014-08-12T05:41:21.943 回答
2

我写了上面的代码，它似乎正在工作。

如果我错了，请纠正我！

public int minimumSum(int[] array)
{
      int counter1, counter2, minimumSum;
      int n = array.length;
      counter1 = array[n-1];
      counter2 = array[n-2];
      // It is assumed that the array is sorted.
      int i = n-3;
      while(i>=0)
      {
          if(counter1 > counter2)
          { 
              counter2 = counter2 + array[i];
          }
          else
          {
              counter1 = counter1 + array[i];
          }
          i--;
      }
      if(counter1 > counter2)
      {
          minimumSum = counter1 - counter2;
      }
      else
          minimumSum = counter2 - counter1;
      return minimumSum ;
}
于 2014-08-12T03:19:51.747 回答
2

排序在这里不起作用，因为这不能像 0-1 背包那样通过贪婪方法解决。你可以这样想，数组中的每个元素都有 2 个选择，要么是负数，要么是正数。您可以通过选择一个数字（一个分支）或不选择它（另一个分支）来开发递归解决方案

这是我所说的实现。可以通过多种方式改进代码。抱歉，如果评论很少。我的时间不多了。

#include "iostream"
#include <algorithm>
using namespace std;

int *arr,*flag,mini=1000; int* sol; //Flag array is used to see which all elements are selected in that call of the function

void find_difference(int* arr,int* flag,int n,int current,int *sol)
{
if(current==n)return;

int sum0=0, sum1=0,entered=0;
flag[current]=1;              //Selecting the current indexed number
for (int i = 0; i < n; ++i)
{
    if(flag[i]==0)
    {
        sum0=sum0+arr[i];
    }
    else
    {
        sum1=sum1+arr[i];
    }
}
    if(abs(sum0-sum1)<mini)
    {
        mini=abs(sum0-sum1);
        for (int j = 0; j < n; ++j)
        {
            sol[j]=flag[j];    //Remebering the optimal solution
        }
    }
find_difference(arr,flag,n,current+1,sol);  //Moving to the next index to perform the same operation (selecting or not selecting it)
flag[current]=0;                 // Not selecting it
for (int i = 0; i < n; ++i)
{
    if(flag[i]==0)
    {
        sum0=sum0+arr[i];
    }
    else
    {
        sum1=sum1+arr[i];
    }
}
    if(abs(sum0-sum1) < mini)
    {
        mini=abs(sum0-sum1);
        for (int j = 0; j < n; ++j)
        {
            sol[j]=flag[j];
        }
    }
find_difference(arr,flag,n,current+1,sol);
}

int main(int argc, char const *argv[])
{
int n;
cout<<"Enter size: ";
cin>>n;
cout<<"Enter the numbers: "
arr= new int[n];
flag= new int[n];
sol= new int[n];
for (int i = 0; i < n; ++i)
{
    cin>>arr[i];
    flag[i]=0;
    sol[i]=0;
}

find_difference(arr,flag,n,0,sol);

cout<<"Min = "<<mini<<endl;
cout<<"One set is: ";
for (int i = 0; i < n; ++i)
{
    if (sol[i]==1)
    {
        cout<<arr[i]<<" ";
    }
}
cout<<"\nOther set is: ";
for (int i = 0; i < n; ++i)
{
    if (sol[i]==0)
    {
        cout<<arr[i]<<" ";
    }
}
cout<<"\n";
return 0;
}
于 2013-11-15T12:59:15.980 回答