题目链接 https://www.acwing.com/problem/content/6/

我想的是线预处理出每个二进制位代表的数，然后再后面一个一个加起来判断是不是符合体积要求；不满足就恢复成上一步的体积，就这样进行dp最后的答案就是偏离了一些正确答案，大佬快救救TAT

错误的代码：

#include<iostream>
#include<cmath>
using namespace std;
const int N=99999;
 int n,val,w[N],vau[N],s[N];
long long int  qui[N];
long long int f[10000];
int pos=(int)log2(200000);
void init()
{
    qui[0]=1;
    pos+=2;
    for(int i=1;i<=pos;i++){
        qui[i]=qui[i-1]*2;
    }
}
int main()
{
    init();
   cin>>n>>val;
    for(int i=0;i<n;i++)
    {
        cin>>w[i]>>vau[i]>>s[i];
        for(int j=val;j>=0;j--)
        //for(int j=0;j<=val;j++)
        { 
            int room=0;
            for(int k=pos;k>=0;k--)
            {
                room+=qui[k]*w[i];
                if(j>=room)
                {
                    if(room/w[i]>s[i])
                  {
                    room-=qui[k]*w[i];
                    continue;
                  }
                     f[j]=max(f[j],f[j-room]+room/w[i]*vau[i]);
                }
                else room-=qui[k]*w[i];
            }
        }
    }
    cout<<f[val];
}

提问于27天前

凝幽

208