题目：硬币问题。有n种硬币，面值分别为V1, V2, …, Vn，每种都有无限多。给定非负整数S， 可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值和最大值。 1≤n≤100，0≤S≤10000，1≤Vi≤S。

分析：这个模型和上一题类似，但也有一些明显的不同之处：上题并没有确定路径的起点和终点（可以把任意矩形放在第一个和最后一个），而本题的起点必须为S，终点必须为0；点固 定之后“最短路”才是有意义的。

思路：类似完全背包。输出方案用了两种方法。

//记录路径

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int  v[105];
int s, n;
int MAXdp[105];
int MINdp[105];
int L_max[105], L_min[105];

int main()
{
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
    }
    MAXdp[0]=MINdp[0]=0;
    for(int i=1;i<=s;i++)
    {
        MAXdp[i]=0;
        MINdp[i]=(1<<31)-1;
    }
    for(int i=1;i<=s;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i>=v[j])
            {
                if(MAXdp[i]<MAXdp[i-v[j]]+1)
                {
                    MAXdp[i]=MAXdp[i-v[j]]+1;
                    L_max[i]=j;//得到i的上一步选择，记录路径
                }
                if(MINdp[i]>MINdp[i-v[j]]+1)
                {
                    MINdp[i]=MINdp[i-v[j]]+1;
                    L_min[i]=j;//得到i的上一步选择，记录路径
                }
            }
        }
    }
    printf("%d %d\n",MAXdp[s],MINdp[s]);

    for(int i=s;i;)
    {
        printf("%d ",L_max[i]);
        i-=v[L_max[i]];
    }
    printf("\n");
    for(int i=s;i;)
    {
        printf("%d ",L_min[i]);
        i-=v[L_min[i]];
    }
    printf("\n");

    return 0;
}

turn 0;
}

//回溯路径

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int  v[105];
int s, n;
int MAXdp[105];
int MINdp[105];
int L_max[105], L_min[105];

int print_ans(int *d, int s)//回溯
{
    if(s==0)
    {
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        if(s>=v[i]&&d[s]==d[s-v[i]]+1)
        {
            printf("%d ",i);
            print_ans(d, s-v[i]);
            break;
        }
    }
}

int main()
{
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
    }
    MAXdp[0]=MINdp[0]=0;
    for(int i=1;i<=s;i++)
    {
        MAXdp[i]=0;
        MINdp[i]=(1<<31)-1;
    }
    for(int i=1;i<=s;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i>=v[j])
            {
                MAXdp[i]=max(MAXdp[i], MAXdp[i-v[j]]+1);
                MINdp[i]=min(MINdp[i], MINdp[i-v[j]]+1);
            }
        }
    }
    printf("%d %d\n",MAXdp[s],MINdp[s]);
    print_ans(MAXdp, s);
    printf("\n");
    print_ans(MINdp, s);
    printf("\n");

    return 0;
}