2038: 简化型背包【运行错误的来看】我不用DP啦，我要用暴力！

我很雾刺的一件事！！！

DP他就是运行错误！（我也不知道为什么）

本来想看一看别人的题解用的DP都是怎么写的，但是：竟然没人写DP！

来吧看一下大师是怎么RE的：

#include<iostream>
#define ll long long
using namespace std;
    int f[10007][10007];
    int W,V,p,v,w;
int main(){
    cin>>V>>W;
    int s=5;
    while(s--){
        cin>>p>>v>>w;
        for(int i=V;i>=v;i--)
            for(int j=W;j>=w;j--)
                f[i][j]=max(f[i][j],f[i-v][j-w]+p);
    }
    cout<<f[V][W];
    return 0;
}

如果有哪位大好人看出我哪里出问题了评论区告诉我一下谢谢

那好吧沉睡的野兽，苏醒了，题你不敬我，我就打暴力：

思路很简单！

直接套上五个for跑就行了，复杂度是O(2^5)很快：

#define FOR(a) for(int a=0;a<=1;a++)

    FOR(a)
        FOR(b)
            FOR(c)
                FOR(d)
                    FOR(e)

具体地，每次我们只要当空间和重量都满足条件的前提下，更新一下价值的最大值就可以了：

if(vi<=V&&wi<=W)pi>M?M=pi:1;

那么最后晒完整高清无码代码

#include<iostream>
#define FOR(a) for(int a=0;a<=1;a++)
using namespace std;
    int V,W,p[6],v[6],w[6];
    int M=-1000000007;
int main(){
    cin>>V>>W;
    for(int i=1;i<=5;i++)cin>>p[i]>>v[i]>>w[i];
    FOR(a)
        FOR(b)
            FOR(c)
                FOR(d)
                    FOR(e){
                        int vi=0,wi=0,pi=0;
                        if(a)vi+=v[1],wi+=w[1],pi+=p[1];
                        if(b)vi+=v[2],wi+=w[2],pi+=p[2];
                        if(c)vi+=v[3],wi+=w[3],pi+=p[3];
                        if(d)vi+=v[4],wi+=w[4],pi+=p[4];
                        if(e)vi+=v[5],wi+=w[5],pi+=p[5];
                        if(vi<=V&&wi<=W)pi>M?M=pi:1;
                    }
    cout<<M;        
    return 0;
}

你能说它暴力么！要时间，2^5这多快啊！要空间，又用不上DP的f[10007][10007]，真的是：WULAWULA！