题目描述

这里面我直接写题解了，之前学的背包问题我们可以很快得到转移方程：
f[i][j]=max(f[i+1][j],f[i+1][j-v[i]]+w[i])，
语言描述一下吧，就是我们当前这个的最大值来源于 上一个状态的j-v[i]的体积，加上w[i]的价值
可以得到我们的枚举方程。。。。。。

但是我们最后一个大样例没过啊，
仔细想一下，有一个相同的体积物品，但是价值不同，且前面的价值较大。
那我们的算法不是可能被卡掉吗（。。。。。。），vol-v[i]<0
那我们直接在判断上加入一个vol>=v[i]

样例

C++ 代码

#include<bits/stdc++.h>
#define re register
using namespace std;

const int N=2e3+10;
int f[N][N];
int v[N],w[N];
int n,m;

int main()
{
//  freopen("a.in","r",stdin);
    scanf("%d %d",&n,&m);
    for(re int i=1;i<=n;++i)
        scanf("%d %d",&v[i],&w[i]);

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

    int vol=m;
    for(re int i=1;i<=n;++i)
    {
        if(f[i][vol]==f[i+1][vol-v[i]]+w[i] && v[i]<=vol)
        {
            printf("%d ",i);
            vol-=v[i];
        }
    }

    return 0;
}