2 条题解

  • 1
    @ 2018-05-27 11:52:21

    补充楼下大佬 二进制优化过的代码

    #include "bits/stdc++.h"
    using namespace std;
    int cont[10001],w[100001],c[100001],dp[10001];
    int  main()
    {
        int n,v;
        cin>>n>>v;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&c[i],&w[i],&cont[i]); 
        }
        int nl=n;
        for(int i=1;i<=n;i++)
        {
                int x=1;
                while(cont[i]>x)
                {
                    nl++;
                    w[nl]=w[i]*x;
                    c[nl]=c[i]*x;
                    cont[i]-=x;
                    x*=2;
                }
                w[i]=w[i]*cont[i];
                c[i]=c[i]*cont[i];
        }
        for(int i=1;i<=nl;i++)
        {
            for(int j=v;j>=c[i];j--)
            {
                dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
            }
        }
        cout<<dp[v];
    }
    

    一定要注意数据有0个的情况!!!!!

  • 1
    @ 2018-05-27 11:11:43

    无优化

    #include"bits/stdc++.h"
    using namespace std;
    int v[10001];
    int w[10001];
    int s[1001];
    int f[10001]; 
    int main()
    {
        int n,m;
        cin>>n>>m;
        int i,j;
        int k;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d",&v[i],&w[i],&s[i]);
        }
        for(i=1;i<=n;i++)
        {
            for(j=m;j>=0;j--)
            {
                for(k=1;k<=s[i];k++)
                {
                    if(j<k*v[i])break;
                    f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
                }
            }
        }
        cout<<f[m];
        return 0; 
    } 
    
  • 1

信息

难度
7
分类
(无)
标签
递交数
84
已通过
18
通过率
21%
上传者