过了这么久 正确理解01背包应该从记忆化搜索开始
这里对数字的取或者不取实际上就是一个01背包的模型 不过这里要求的是满包问题 那么我们动态便利的过程需要做一点 处理只有从0开始的能够向上更新
在就是一个最小路径更新 可以用排序 （排序以后最先到达的满足条件的就是我们需要的路线） 也可以多次到达的时候向小的更新
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#define inf 100009
using namespace std;
int n,m;
int a[],dp[],pre[];
bool cmp(int x,int y)
{
return x<y;
}
int main()
{
cin>>n>>m;
for(int i=;i<=n;i++) cin>>a[i];
fill(dp,dp+,-inf);//满包处理1
for(int i=;i<=m;i++) pre[i]=i;
dp[]=;// 满包处理2
sort(a+,a++n,cmp);
for(int i=;i<=n;i++)
{
for(int j=m;j>=a[i];j--)
{
if(dp[j-a[i]] < ) continue;// 对于没有包含的情况 直接跳过 if(dp[j] <= dp[j-a[i]]+)
{
dp[j]=dp[j-a[i]]+;
if(pre[j] > j-a[i])pre[j]=j-a[i];//
}
}
}
if(dp[m] <= ) cout<<"No Solution"<<endl;
else
{
vector<int> line;
line.clear();
int temp=m;
//cout<<pre[m]<<endl;
while(temp!=)
{
line.push_back(temp-pre[temp]);
temp=pre[temp]; }
for(int j=line.size()-;j>=;j--)
{
if(j == line.size()- ) cout<<line[j];
else cout<<' '<<line[j];
}
cout<<endl;
}
return ;
}