c4 L3-001 找零钱 （简单01背包-输出最小字典序解（用vector保存当前最优解））

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e4+7;
int a[N];
bool dp[107];
vector < vector <int> > ans (107);
int n,m;
bool cmp (vector<int> x, vector<int> y)  {// 不用考虑x与y得大小 因为至少一个数不同 或者全部相同
    for (int i=0;i<x.size();i++) {
        if (x[i]<y[i])  return 1;
        else if (x[i]>y[i])  return 0;
    }
    return 0;
}
int main ()
{
    scanf ("%d %d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf ("%d",&a[i]);
    sort (a+1,a+1+n);
    dp[0]=1;
    for (int i=1;i<=n;i++) {
        for (int j=m;j>=a[i];j--) {
            if (dp[j-a[i]])  {
                vector <int> tmp=ans[j-a[i]];
                tmp.push_back(i);
                if (!dp[j])  { dp[j]=1;ans[j]=tmp; }
                else if (cmp (tmp,ans[j]))  ans[j]=tmp;
            }
        }
    }
    if (!dp[m])  printf ("No Solution
");
    else  {
        printf ("%d",a[ans[m][0]]);
        for (int i=1;i<ans[m].size();i++)
            printf (" %d",a[ans[m][i]]);
        printf ("
");
    }
    return 0;
}