题解 | #购物单#

//背包问题变形
#include
#include
int main(void)
{
    int money, num;
    scanf("%d%d", &money, &num);
    int satisfy[60][4];
    int value[60][4];
    memset(satisfy, 0, sizeof(satisfy));
    memset(value, 0, sizeof(value));
    for (int i = 0; i < num; i++)
    {
        int v, p, q;
        scanf("%d%d%d", &v, &p, &q);
        if (q == 0)//如果i物品是主件
        {
            value[i][0] = v;
            satisfy[i][0] = v * p;
        }
        else if (q != 0)//如果i物品是附件
        {
            if (value[q - 1][1] == 0)//该物品是附件1
            {
                value[q - 1][1] = v;
                satisfy[q - 1][1] = v * p;
            }
            else if (value[q - 1][1] != 0)//该物品是附件2
            {
                value[q - 1][2] = v;
                satisfy[q - 1][2] = v * p;
                value[q - 1][3] = value[q - 1][2] + value[q - 1][1];
                satisfy[q - 1][3] = satisfy[q - 1][2] + satisfy[q - 1][1];
            }
        }
    }
    //二维数组需要补充主件价值
    for (int i = 0; i < num; i++)
    {
        for (int j = 1; j < 4; j++)
        {
            if (value[i][0] != 0)//必须是主件才可以加
            {
                value[i][j] += value[i][0];
                satisfy[i][j] += satisfy[i][0];
            }
        }
    }
    //开始动态规划
    int dp[32000] = { 0 };//要选择用一维数组还是二维做动态规划，这里不知道主件的数量，所以使用一维数组
    for (int i = 0; i < num; i++)//外循环为物品数量
    {
        if (value[i][0] == 0)//不单独购买附件
            continue;
        /*for (int k = 0; k <= 3; k++)
        {
            printf("%d ", satisfy[i][k]);
        }*/
        for (int j = money; j >=0; j -= 10)
            //为什么不从0开始遍历？
            //因为会出现重复购买的情况，所以外层循环正向遍历物品，内层循环反向遍历背包容量
        {
            for (int k = 0; k <= 3; k++)//遍历四种主件附件组合
            {
                if (j >= value[i][k])//如果选择购买ik组合
                {
                    dp[j] = (dp[j] > satisfy[i][k] + dp[j - value[i][k]]) ? dp[j] : (satisfy[i][k] + dp[j - value[i][k]]);
                }
            }
        }
    }
    printf("%d", dp[money]);
    return 0;
}