洛谷p1064 金明的预算方法

有附带条件的01背包

要那附件必须拿主件

因为一个主件最多有两个附件，所以每次遇到主件可能有四种选择

1、只拿主件

2、拿主件和一号附件

3、拿主件和二号附件

4、都拿

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#define INF 0x3f3f3f3f

using namespace std;

const int MAXV = ;

const int MAXN = ;

int dp[MAXV];

int p[MAXN], q[MAXN], v[MAXN];

int N, M;

void slv()

{

    memset(dp, , sizeof(dp));

    bool k1, k2;

    int t1, t2;

    for(int i = ; i <= N; i++)

    {

        t1 = t2 = ;

        k1 = k2 = false;

        if(q[i] == )

        {

            k1 = k2 = false;

            for(int k = i+; k <= N; k++)

            {

                if(q[k] == i)

                {

                    t1 = k;

                    k1 = true;

                    break;

                }

            }

            for(int k = t1+; k <= N; k++)

            {

                if(q[k] == i)

                {

                    t2 = k;

                    k2 = true;

                    break;

                }

            }

            for(int s = M; s >= v[i]; s--)

            {

                dp[s] = max(dp[s], dp[s-v[i]] + v[i]*p[i]);

                if(s-v[i]-v[t1] >=  && k1)

                {

                    dp[s] = max(dp[s], dp[s-v[i]-v[t1]] + v[i]*p[i] + v[t1]*p[t1]);

                }

                if(s-v[i]-v[t2] >=  && k2)

                {

                    dp[s] = max(dp[s], dp[s-v[i]-v[t2]] + v[i]*p[i] + v[t2]*p[t2]);

                }

                if(s-v[i]-v[t1]-v[t2] >=  && k1 && k2)

                {

                    dp[s] = max(dp[s], dp[s-v[i]-v[t1]-v[t2]] + v[i]*p[i] + v[t1]*p[t1] + v[t2]*p[t2]);

                }

            }

        }

    }

    printf("%d\n", dp[M]);

}

int main()

{

    scanf("%d%d", &M, &N);

    for(int i = ; i <= N; i++)

        scanf("%d%d%d", &v[i], &p[i], &q[i]);

    slv();

    return ;

}