(背包九讲)二维费用背包 短代码

回复帖子 返回题目

@ uhgariej 2017-12-07 20:08

//不会这题的,可以去看看《《背包九讲》》,里面讲的很详细。我这里只是将他的伪代码写成c++而已。

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e2+10;
int f[maxn][maxn];
int n,M,T;
int main(){
    cin>>n>>M>>T;
    for(int i=1,x,y;i<=n;++i){
        cin>>x>>y;
        for(int k=M;k>=x;--k)
            for(int t=T;t>=y;--t)
                f[k][t]=max(f[k][t],f[k-x][t-y]+1);
    }
    cout<<f[M][T]<<endl;
    return 0;
}