背包问题求具体的方案：如果是需要按照字典序排列的话，需要在状态计算的时候倒着计算
f[i][j]表示从第n件物品到第i件物品，体积不超过j的前提下的最大收益
因此第i件物品如果不选的话，状态就是f[i+1][j],反之f[i+1][j-v[i]]+w[i];
然后在计算的时候倒着往前算一遍——也就是从1枚举到n,只有这样的话才能确保字典序最小

AcWing 12. 背包问题求具体方案

#include<iostream>

using namespace std;

const int N = 1010;

int f[N][N];
int n,m;
int w[N],v[N];

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)cin >> v[i] >> w[i];

    for(int i=n;i>=1;i--)
        for(int j=0;j<=m;j++)
    {
        f[i][j]=f[i+1][j];
        if(j>=v[i])f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
    }

    int j=m;
    for(int i=1;i<=n;i++)
        if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i])
        //注意这个时候体积必须得可以装得下这个物品（可能是从其他的状态转移过来的，所以需要特判一下）
        {
            j-=v[i];
            cout << i << " ";
        }
    return 0;
}

AcWing 1021. 货币系统
多重背包的应用——若干钱币判断有多少种可以组合成给定的方案

f[i][j]：表示在前i中钱币中，选择体积恰好为j的方案数
计算集合的方式：
第i个钱币选或者不选，f[i][j]=f[i-1][j];
选的话通过枚举式子发现(基础课里有)，f[i][j]+=f[i][j-v[i]]；
然后可以将状态优化为一维的，根据上次y总说的规律，除了多重背包的朴素版和单调队列版本，其余的大多都是枚举体积从大到小
易错点：f[0]=1，在没有纸币的情况下，只有这一种方案可以凑成0；第二：注意方案数可能过多，导致超出int范围

#include<iostream>

using namespace std;

const int N = 3010;

long long f[N];
int n,m;

int main()
{
    cin >> n >> m;
    f[0]=1;
    for(int i=0;i<n;i++)
    {
        int x;
        cin >> x;
        for(int j=x;j<=m;j++)
            f[j]+=f[j-x];
    }
    cout << f[m] << endl;
    return 0;
}

AcWing 532. 货币系统
题目隐含的信息：新的货币就是旧货币里的那些唯一的货币——不能被其他货币表示
因此我们需要首先将货币排序，然后将货币从小到大来枚举，看是否能被前i-1个货币表示，如果不能的话则res++;
f[i][j]与上一个题目的状态表示一致，只不过需要将判断条件转换为f[i-1][a[i]]
因此在写一维优化的时候需要将判断条件提前

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 110, M = 25010;

int f[M];
int a[N];
int n;

int main()
{
    int T;
    cin >> T;

    while(T--)
    {
        cin >> n;
        for(int i=1;i<=n;i++)cin >> a[i];
        sort(a+1,a+1+n);

        memset(f,0,sizeof f);
        f[0]=1;
        int res=0;
        for(int i=1;i<=n;i++)
        {
            if(!f[a[i]])res++;
            //一维状态下不可更换位置——更换的话表示的是f[i][a[i]]不符合题意
            for(int j=a[i];j<=a[n];j++)
                f[j]+=f[j-a[i]];
        }
        cout << res << endl;
    }
}

AcWing 487. 金明的预算方案
题意：选了附件的话一定要选择主件
由于附件的个数很少因此在这里可以通过二进制的枚举，来判断方案
如果有两个附件的话，可以通过枚举一个主件或者一个主件一个附件，或者一个主件和另一个附件或者一个主件和两个附件，来枚举答案

#include<iostream>
#include<vector>

using namespace std;

typedef pair<int,int> pii;
const int N = 70, M = 32010;

pii mas[N];
vector<pii> ser[N];
int f[M],n,m;

int main()
{
    cin >> m >> n;
    for(int i=1;i<=n;i++)
    {
        int v,p,q;
        cin >> v >> p >> q;
        if(!q)mas[i]={v,v*p};
        else ser[q].push_back({v,v*p});
        //表示的是q这个主件的所插入的附件
    }

    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
        {
            for(int k=0;k<1<<ser[i].size();k++)
            //注意枚举的是附件的元素个数
            {
                int v=mas[i].first,w=mas[i].second;
                for(int s=0;s<ser[i].size();s++)
                    if(k>>s&1)
                     {
                         v+=ser[i][s].first;
                         w+=ser[i][s].second;
                     }
                if(j>=v)f[j]=max(f[j],f[j-v]+w);
            }
        }
    cout << f[m] << endl;
    return 0;
}