最近在学习动态规划，PAT中的这一题就是一个典型的dp问题。
这一题和01背包问题很类似，M相当于背包问题中的背包容量，硬币面值相当于每件物品的重量，背包问题中要求物品价值最大，这里要求物品总重（面值和）等于M，从可选方案中选择最优的是根据给定的比较方法。
我们解决问题的难点：如何选择出最小的序列？
首先来看递归式：L(i, j)表示在前i号硬币中选择，并且总价值小于等于j的序列的最大面值和。这里我们不要求等于j，只要尽量接近j就可以了。a[i]是i号硬币的面值，则递归式如下：
L(i, j) = 0
i == 0 || j == 0
= L[i - 1, j]
a[i] > j
= max(L(i - 1, j - a[i]) + a[i], L(i - 1, j))
a[i] <= j
自底向上填表之后，回溯一遍就可以得到所得序列。
但是想要保证序列“最小”，就必须将原面值递减排序。在回溯中每次遇到L(i - 1, j - a[i]) + a[i]这种情况，就决定选择a[i]，因为此时a[i]总是最小的。
//类似于01背包的DP
//降序排列是关键！！！
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
int N, M;
vector<int> v;
vector<vector<int>> l;
void dp()
{
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= M; j++)
{
if(v[i] > j)
l[i][j] = l[i - 1][j];
else
l[i][j] = l[i - 1][j - v[i]] + v[i] > l[i - 1][j] ? l[i - 1][j - v[i]] + v[i] : l[i - 1][j];
}
}
if(l[N][M] != M)
{
cout<<"No Solution"<<endl;
return;
}
//回溯输出选取的序列
int j = M;
int i = N;
//cout<<" ";
while (j > 0)
{
if(l[i][j] == l[i - 1][j - v[i]] + v[i])
{
cout<<v[i];
j -= v[i];
i -= 1;
if(j != 0) cout<<" ";
}
else
{
i -= 1;
}
}
cout<<endl;
}
bool cmp(const int &a, const int &b)
{
return a > b;
}
int main()
{
//fstream cin("a.txt");
cin>>N>>M;
v.push_back(0);
for(int i = 0; i < N; i++)
{
int tmp;
cin>>tmp;
v.push_back(tmp);
}
sort(v.begin() + 1, v.end(), cmp);
for(int i = 0; i <= N; i++)
{
vector<int> tmp;
for(int j = 0; j <= M; j++)
tmp.push_back(0);
l.push_back(tmp);
}
dp();
}