01背包 样例都没过??!

回复帖子

@EthanWu 2018-10-13 10:02 回复

为什么啊啊啊啊啊

#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<queue>
#include<algorithm>
#include<stack>
using namespace std;
int n,m;
int c[3405],w[3405],f[3405][12885];
int main()
{

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    for(int j=m;j>=0;j--)
    {
        if(w[i]<=j)
        {
            f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);         
        }
        else f[i][j]=f[i-1][j];
    }
    cout<<f[n][m]<<endl;
    return 0;
}
@disangan233  2018-10-13 10:05 回复 举报

01背包不是这么写的。。不能$j>=0$。。。

#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<queue>
#include<algorithm>
#include<stack>
using namespace std;
int n,m;
int c[3405],w[3405],f[12885];
int main()
{

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>c[i]>>w[i];
    for(int i=1;i<=n;i++)
    for(int j=m;j>=c[i];j--)
    f[j]=max(f[j],f[j-c[i]]+w[i]);         
    cout<<f[m]<<endl;
    return 0;
}

这样差不多了吧qwq

@disangan233  2018-10-13 10:08 回复 举报

@EthanWu 这样好看点

#include<bits/stdc++.h>
using namespace std;
#define re register int
int n,m,c[3405],w[3405],f[12885];
char did;
#define ak *
inline int read()
{
    re ioi=1,cz=0;did=getchar();
    while(!isdigit(did))ioi=did=='-'?-1:ioi,did=getchar();
    while(isdigit(did))cz=(cz<<3)+(cz<<1)+did-'0',did=getchar();
    return cz ak ioi;
}
int main()
{
    n=read(),m=read();
    for(re i=1;i<=n;i++)
    c[i]=read();w[i]=read();
    for(re i=1;i<=n;i++)
    for(re j=m;j>=c[i];j--)
    f[j]=max(f[j],f[j-c[i]]+w[i]);         
    cout<<f[m]<<endl;
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。