根据背包九讲,自己写的泛化背包,从第三个点开始wa
查看原帖
根据背包九讲,自己写的泛化背包,从第三个点开始wa
323744
littlecyber楼主2020/8/1 13:23

有大佬能帮看看哪错了吗QAQ

#include <bits/stdc++.h>
#define memset(a,b) memset(a,b,sizeof(a))
#define maxn 60+5
#define maxm 32000+10
using namespace std;
vector<int> root;
int dp[maxn][maxm],v[maxn],w[maxn],idx;
int e[maxn],ne[maxn],h[maxn];
int n,m;
void add(int fa,int son){
    e[idx]=son;
    ne[idx]=h[fa];
    h[fa]=idx;
    idx++;
}
void dfs(int fa){
    for(int i=h[fa];i!=-1;i=ne[i]){
        if(h[e[i]]!=-1)
        dfs(e[i]);
        for(int j=n-w[fa];j>=0;j-=10)
            for(int k=0;k<=j;k+=10)dp[fa][j]=max(dp[fa][j],dp[fa][j-k]+dp[e[i]][k]);//泛化背包
    }
    for(int j=n;j>=w[fa];j-=10)dp[fa][j]=dp[fa][j-w[fa]]+v[fa];//包含主件在内的所有取值可能
    for(int j=0;j<w[fa];j+=10)dp[fa][j]=0;
}
int main()
{
    memset(h,-1);
    cin>>n>>m;int tp,ro;idx=0;
    for(int i=0;i<m;i++){
        cin>>w[i]>>tp>>ro;
        v[i]=w[i]*tp;
        if(ro)add(ro-1,i);
        else root.push_back(i);
    }
    for(int i=0;i<root.size();i++)
        //if(h[i]!=-1)
        dfs(root[i]);
    for(int i=0;i<root.size();i++){
        int t=root[i];
        for(int j=n;j>=0;j-=10){
            //if(h[t]!=-1)
                for(int k=0;k<=j;k+=10)dp[m][j]=max(dp[m][j],dp[m][j-k]+dp[t][k]);
            //else dp[m][j]=max(dp[m][j],dp[m][j-w[t]]+v[t]);
        }
        cout<<root[i]<<" ";
    }
    cout<<dp[m][n];
    return 0;
}
2020/8/1 13:23
加载中...