找到任何解决方案，更不用说最大的解决方案了，称为subset sum problem。它是NP完全的，最有效的已知算法是exponential running time。

因此，贪婪算法无法解决此问题。您不会比某种backtracking search做得更好。使用动态编程的解决方案实际上将等同于回溯搜索，只是实现方式有所不同。因此，比较非常短：贪婪不起作用，但动态编程可以。

您如何将贪婪方法与动态编程方法进行比较？

贪婪的方法在您的情况下将失败，因为您将永远不知道何时跳过或拿硬币来获得最佳答案。您必须通过包含/排除每个硬币来尝试所有可能的解决方案。

例如，您可以使用相同的硬币更改算法，通过动态编程来做到这一点，但避免多次取同一枚硬币

从上到下的递归方法：

int n = 4,k = 11;
int dp[4][12],coins[] = {1,2,3,5};

int solve(int i = 0,int sm = k) {
    // base case for when the sum is reached
    if (sm == 0) {
        return 0;
    }
    // took more than needed coins or reached the end without reaching sum
    if (sm < 0 || i == n) {
        return 1000000000;
    }
    // check if dp value already calculated
    int& ret = dp[i][sm];
    if (~ret) {
        return ret;
    }
    // otherwise,try taking the coin or skipping it
    return ret = min(solve(i+1,sm),1 + solve(i+1,sm-coins[i]));
}
int main() {
    memset(dp,-1,sizeof dp);
    cout << solve() << endl;
 return 0;
}
// output: 4