题目描述：
东东开车出去泡妞(在梦中)，车内提供了 n 张CD唱片，已知东东开车的时间是 n 分钟，他该如何去选择唱片去消磨这无聊的时间呢
假设:
- CD数量不超过20张
- 没有一张CD唱片超过 N 分钟
- 每张唱片只能听一次
- 唱片的播放长度为整数
- N 也是整数
我们需要找到最能消磨时间的唱片数量，并按使用顺序输出答案（必须是听完唱片，不能有唱片没听完却到了下车时间的情况发生）
本题是 Special Judge
思路：
- 题目很简单，就是01背包，但是要输出路径，但是这里的路径不要求是字典序最小
- 可以直接逆着递推过程去打印方案，没什么问题
- 而且可以发现，下述代码打印的方案不一定是字典序最小的，因为是逆向打印
- 研究了很长时间如何字典序打印路径和为什么逆向打印是不可行的，感觉还是很难理解，我感觉应该再熟悉一下DP然后再来解决打印最小字典序这个问题
总结：
可以按照递推或搜索的过程来逆向打印路径
代码：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN=1e4+5;
int f[25][MAXN];
int w[25]; //w[i]==v[i]
//输出到达 只考虑前i个物品容量为j时最大值 的路径
void print(int i,int j)
{
if(i<=0) return;
if(f[i][j]==f[i-1][j]) //第i个物品没选
{
print(i-1,j);
}
else if( j-w[i]>=0 && f[i][j]==f[i-1][j-w[i]]+w[i]) //第i个物品选了
{
print(i-1,j-w[i]);
cout<<w[i]<<' ';
}
}
int main()
{
int N,M;
while( scanf("%d %d",&N,&M)==2 )
{
memset(f,0,sizeof(f));
for(int i=1;i<=M;i++)
scanf("%d",w+i);
for(int i=1;i<=M;i++)
for(int j=0;j<=N;j++)
{
f[i][j]=f[i-1][j];
if( j>=w[i] )
f[i][j]=max(f[i][j],f[i-1][j-w[i]]+w[i]);
}
print(M,N);
cout<<"sum:"<<f[M][N]<<endl;
}
return 0;
}