c++ - 带数字的优化算法

Question

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

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!";
 }

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

Answer 1

问题是 subset sum problem 的变体，即 NP-Hard .

NP-Hard 问题是这样一个问题(除其他事项外)- 没有已知的多项式解，因此“首先获得最高值”的贪婪方法对它失败。

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

This page包含问题的解释和可能的解决方案。