1 条题解

  • 0
    @ 2021-02-06 21:48:47

    本题是0/1背包
    价值v要乘上重量w
    开long long!数组要大!
    我关于0/1背包的讲解:【精讲】DP经典问题——0/1背包问题

    #include<cstdio>
    using namespace std;
    long long n,t,w,v,f[100010];
    long long max(long long x,long long y){
        if(x>y)return x;
        else return y;
    }
    int main(){
        scanf("%d%d",&n,&t);
        for(long long i=1;i<=t;i++)
        {
            scanf("%d%d",&w,&v);
            v*=w;
            for(long long j=n;j>=w;j--)
                f[j]=max(f[j],f[j-w]+v);        
        }
    
        printf("%d",f[n]);
    }
    
  • 1

信息

难度
9
分类
(无)
标签
递交数
6
已通过
3
通过率
50%
被复制
1
上传者