题解 | #购物单#

思路：
1、把价格和价值分别保存起来。price//价格 value//价值
2、用dp[i][j]表示前i个物品，价格为j时的最大价值。
3、得到状态转移方程 //k表示k种情况
/* 物品的选项
1、仅选主件
2、主件 + 附件1
3、主件 + 附件2
4、主件 + 附件1 + 附件2
*/ 所以k == 4

**dp[i][j] = MAX(dp[i-1][j], dp[i-1][j-price[i-1][k]] + value[i-1][k]);**

表示取每种情况的最大值

#include <stdio.h>

#define MAX(a, b) ((a>b)?(a):(b))

int main()
{
    int N = 0;    //钱
    int m = 0;    //物品数
    scanf("%d %d", &N, &m);
    /* 物品的选项
    1、仅选主件
    2、主件 + 附件1
    3、主件 + 附件2
    4、主件 + 附件1 + 附件2
    */
    int price[m][4];   //4种组合的全部价格
    int value[m][4];   //4种组合的满意度 = 价格 * 重要度(价值)
    memset(price, 0, m*4*sizeof(int));
    memset(value, 0, m*4*sizeof(int));

    int v = 0;    //价格
    int p = 0;    //重要度
    int q = 0;    //物品
    for(int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &v, &p, &q);
        if(q == 0)    //表示主件
        {
            price[i][0] = v;
            value[i][0] = v * p;
        }
        else
        {
            if(price[q-1][1] == 0)
            {
                //附件1
                price[q-1][1] = v;
                value[q-1][1] = v * p;
            }
            else if(price[q-1][2] == 0)
            {
                //附件2
                price[q-1][2] = v;
                value[q-1][2] = v * p;

                //附件1 + 附件2，
                price[q-1][3] = price[q-1][1] + price[q-1][2];
                value[q-1][3] = value[q-1][1] + value[q-1][2];
            }
        }
    }

    //把主件的价格和满意度，添加到其余三个组合中
    for(int i = 0; i < m; i++)
    {
        for(int j = 1; j < 4; j++)
        {
            price[i][j] += price[i][0];
            value[i][j] += value[i][0];
        }
    }

    int dp[m+1][N+1];
    memset(dp, 0, (m+1)*(N+1)*sizeof(int));

    int max_value = 0;
    for(int i = 1; i < m+1; i++)    //表示m件物品
    {
        for(int j = 1; j < N+1; j++)    //表示N元钱
        {
            max_value = dp[i-1][j];
            for(int k = 0; k < 4; k++)
            {
                if(j - price[i-1][k] >= 0)
                {
                    //说明有足够的钱购买当前物品
                    max_value = MAX(max_value, dp[i-1][j-price[i-1][k]] + value[i-1][k]);
                }
            }
            //dp[i][j]表示前i个物品在钱数为j的情况下获取的最大满意度
            dp[i][j] = max_value;
        }
    }
    printf("%d\n", dp[m][N]);

    return 0;
}