1

给定一个递增顺序的数字列表和一定的总和，我正在尝试实现找到总和的最佳方法。首先使用最大的数字

A sample input would be:
3
1
2
5
11

其中第一行是我们正在使用的数字的数量，最后一行是所需的总和

the output would be:
1 x 1
2 x 5

等于 11

我正在尝试使用标准输入来解释这个https://www.classle.net/book/c-program-making-change-using-greedy-method

这是我到目前为止得到的

#include <iostream>
using namespace std;

int main()
{
 int sol = 0; int array[]; int m[10];

 while (!cin.eof())
  {
   cin >> array[i];  // add inputs to an array
   i++;
  }

 x = array[0]; // number of 
 for (int i; i < x ; i++) {
  while(sol<array[x+1]){
     // try to check all multiplications of the largest number until its over the sum
     // save the multiplication number into the m[] before it goes over the sum;
     //then do the same with the second highest number and check if they can add up to sum

     }
  cout << m[//multiplication number] << "x" << array[//correct index]
  return 0;
} 

   if(sol!=array[x+1])
 {
 cout<<endl<<"Not Possible!";
 }

}

很难找到一种有效的方法来尝试从最大数字开始的所有可能组合？任何建议都会很有帮助，因为我知道我很清楚

4

1 回答 1

4

该问题是子集和问题的变体，即NP-Hard。

NP-Hard 问题是一个问题（除其他外） - 没有已知的多项式解决方案，因此“首先获得最高”的贪婪方法失败了。

然而，对于这个 NP-Hard 问题，有一个使用动态规划的伪多项式解决方案。您可以多次选择每个数字的问题称为 con change 问题。

此页面包含问题的解释和可能的解决方案。

于 2012-10-13T22:39:33.720 回答