题目描述

注意要改状态转移方程，因为从后往前遍历

#include <iostream>
#include <vector>
using namespace std;

const int N=1010;
int v[N],w[N],f[N][N];
vector<int> z;


int main()
{
    int n,m;
    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=1;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(i == n && j >= v[i])
        {
            printf("%d ",i);
            break;
        }
        if(j>=v[i] && (f[i][j]==f[i+1][j-v[i]]+w[i]))
        {
            cout<<i<<" ";
            j=j-v[i];
        }
    }


    return 0;
}

因为要求最小字典序，所以我们把状态转移方程f[i][j]的含义更改为：从第i个物品到最后，体积不超过j的最优解，那么最终目标即求：f[1][m]。

为什么这样更改f的含义就能求得最小字典序呢？

如果f(1,m)=f(2,m−v[1])+w[1]f(1,m)=f(2,m−v[1])+w[1]，说明选取了第1个物品可以得到最优解。
如果f(1,m)=f(2,m)f(1,m)=f(2,m)，说明不选取第一个物品才能得到最优解。
如果f(1,m)=f(2,m)=f(2,m−v[1])+w[1]f(1,m)=f(2,m)=f(2,m−v[1])+w[1]，说明选不选都可以得到最优解，但是为了考虑字典序最小，我们也需要选取该物品。

至于为什么要改状态转移方程呢？

题目要求输出字典序最小的解，假设存在一个包含第1个物品的最优解，为了确保字典序最小那么我们必然要选第一个。那么问题就转化成从2～N这些物品中找到最优解。

输出方案的要点：

1. 每次输出一个方案后，得让current_v 减去 v[i]
2. 判断当前方案可以输入：(j>=v[i] && f[i][j]==f[i+1][j-v[i]]+w[i]

#include <iostream>

using namespace std;

const int N=1010;
int n,m;
int f[N][N],v[N],w[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=1;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(i==n && j>=v[i]) 
        {
            cout<<i;
            break;
        }

        if(j>=v[i] && f[i][j]==f[i+1][j-v[i]]+w[i])
        {
            cout<<i<<" ";
            j=j-v[i];
        }
    }

    return 0;
}