3. 完全背包问题

#include<iostream>
using namespace std;

const int Max = 1010;

int v[Max],w[Max];
int f[Max];

int main(){
    int N,V;
    cin >> N >>V;

    f[0]=0;
    for(int i=1;i<=N;i++){
        cin >> v[i] >> w[i];
    }

    for(int i=1;i<=N;i++){
        for(int j=v[i];j<=V;j++){
        //与01背包问题不同的是01背包是倒序而完全背包为顺序
        //01背包问题：f[i][j]的更新时需要f[i-1][j],而完全背包问题：f[i][j]的更新时需要f[i][j]，因此使用的是正序
            f[j]=max(f[j],f[j-v[i]]+w[i]);

        }
    }

    cout<<f[V]<<endl;
}