20分代码求助。。。

P1064 [NOIP2006 提高组] 金明的预算方案

下划线__ @ 2019-11-12 17:49:33

1,3测试点AC,剩下的WA。 调了一下发现会莫名其妙地在dp[N]中出现一个很大的数字,不知道这个背包到底错在哪里了。 代码如下

#include <cstdio>
using namespace std;
const int MAXN = 4e4;
const int MAXM = 100;
int v[MAXN];        //物品的体积 
int w[MAXN];        //物品的价值 
int ch[MAXN][3];    //子物品的编号 
int dp[MAXN];       //这个不用说了吧 
int N,M;
int main()
{
    scanf("%d %d",&N,&M);

    for (int i = 1;i <= M;++i)
    {
        int a,b,c;
        scanf("%d %d %d",&w[i],&v[i],&c);
        v[i] *= w[i];
        if (c)      //如果是子物品     
        {
            ch[c][++ch[c][0]] = i;  //把编号计入到父物品中 
            ch[i][0] = -1;          //标记自身为子物品   
        }
    }
    for (int i = 1;i <= M;++i)
    {
        if (ch[i][0] == -1)         //如果是子物品就跳过不考虑 
            continue;
        for (int j = N;j >= w[i];--j)   //01背包标准写法 
        {
            dp[j] = max(dp[j],dp[j - w[i]] + v[i]);         //只考虑父物品 
            if (ch[i][1] && j >= w[i] + w[ch[i][1]])        //考虑拿父物品和第一个子物品 
                dp[j] = max(dp[j],dp[j - w[i] - w[ch[i][1]]] + v[i] + v[ch[i][1]]); 
            if (ch[i][2] && j >= w[i] + w[ch[i][2]])        //考虑拿父物品和第二个子物品
                dp[j] = max(dp[j],dp[j - w[i] - w[ch[i][2]]] + v[i] + v[ch[i][2]]); 
            if (ch[i][1] && ch[i][2] && j >= w[i] + w[ch[i][1]] + w[ch[i][2]])      //考虑拿父物品和两个子物品 
                dp[j] = max(dp[j],dp[j - w[j] - w[ch[i][1]] - w[ch[i][2]]] + v[i] + v[ch[i][1]] + v[ch[i][2]]);
        }
    }
    printf("%d",dp[N]);     //dp[N]就为最终答案 
}

by 下划线__ @ 2019-11-13 18:05:47

找到问题了。。。。。。第四个转移方程的中括号错了


|