最多硬币问题

注意dp内部条件判断

/*

最多硬币问题

Sample Input#

3

20

3 5 7

Output#

6

*/

#include <cstdio>

#include <cstring>

#include <iostream>

#include <vector>

using namespace std;

#define INF 1000000000

const int maxn=105;

int n;

int S;

int V[maxn];

int d[maxn];

void input()

{

    cin>>n>>S;

    for(int i = 1; i <= n; i++) cin >> V[i];

}

//这里要注意表示dp的状态值： 因为最小值可能是0， 所以不能用0代表没算过，而是用-1代表没算过。-INF代表不可达。

int dp(int S)

{

    int &ans=d[S];

    if(ans!=-1) return ans;

    ans=-INF;//表示不可达

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

        if(S>=V[i])

        {

            int t = dp(S-V[i]);

            if(t!=-INF)

                ans=max(t+1, ans);

        }

    return ans;

}

void print_ans(int* d, int S){

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

        if(S>=V[i] && d[S-V[i]]+1==d[S])

        {

            cout<<i<< " ";

            print_ans(d, S-V[i]);

            break;

        }

}

int main()

{

    input();

    memset(d, -1, sizeof(d));//-1代表没算过

    d[0]=0;//0的时候，不需要硬币

    int r = dp(S);

    if(r==-INF)

        cout<< "no solution"<<endl;

    else

    {

        cout<< r <<endl;

        print_ans(d, S);

    }

}