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 困難な問題は、(とりわけ) 問題です - そのための既知の多項式解がないため、「最初に最高のものを取得する」という貪欲なアプローチは失敗します。

ただし、この NP 困難な問題には、動的計画法を使用した疑似多項式ソリューションがあります。各数字を複数回選択できる問題は、con change problem と呼ばれます。

このページには、問題の説明と考えられる解決策が含まれています。

于 2012-10-13T22:39:33.720 に答える