（硬币凑数问题）完全背包，求刚好满足总体积为w的物品组合的元素最小值

解题思路:

硬币凑数问题

即完全背包问题，求刚好满足总体积为w的物品组合的元素最小值。

在动态规划过程中，初值和元素转移条件没搞好，如果dp[i]=INT_MAX,那么用

手里的硬币是没法凑出i的，在状态转移dp[j]=min(dp[j],dp[j-a[i]]+1)时，需要加入if(dp[j-a[i]]!=INT_MAX)的判断。所以需要确保dp[j-a[i]]+1为合法条件。

参考代码:

#include<iostream>

#include<cstring>

#include<algorithm>

#include<limits.h>

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int n,m;

    cin>>n;

    int arr[n];

    int max = 0;

    for(int i = 0; i< n; i++)

    {

        cin>>arr[i];

        if(arr[i] > max)

        max = arr[i];

    }

    int res=0,flag=0;

    while(cin>>m&&getchar()!='\n'){

    int dp[m+1];

    for(int i=0; i<= m; i++) dp[i] = INT_MAX;

    dp[0] = 0;

    for( int i = 0; i  < n; i++)

    {

        if(arr[i]<m)

        dp[arr[i]] = 1;

    }

      for(int i=0;i<n;++i)

        for(int j=1;j<=m;++j)

        {

            if(j-arr[i]>=0&&dp[j-arr[i]]!=INT_MAX)

            dp[j]=min(dp[j],dp[j-arr[i]]+1);

        }

        if(dp[m]==INT_MAX){flag=1;break;}

        res+=dp[m];

    }

    if(!flag) cout<<res<<endl;

    else cout<<-1<<endl;

    return 0;

}