题解 | #购物单#

#include <stdio.h>
//背包问题，可将主件与附件视作同一种物品存放在数组相应位置，使得遍历时不出现重复计算（在这里卡了半天）
int max(int a, int b)
{
    return a > b ? a: b;
}
int main()
{
    int N = 0;
    int m = 0;
    scanf("%d %d", &N, &m);
    int val[60][4] = { 0 };
    int weight[60][4] = { 0 };
    int i = 0;
    int j = 0;
    for (i = 0; i < m; i++)
    {
        int v, p, q;
        scanf("%d %d %d", &v, &p, &q);
        if (q == 0)
        {
            val[i][0] = v;
            weight[i][0] = v * p;
        }
        else if (q != 0 && val[q - 1][1] == 0)
        {
            val[q - 1][1] = v;
            weight[q - 1][1] = v * p;
        }
        else
        {
            val[q - 1][2] = v;
            val[q - 1][3] = val[q - 1][1] + val[q - 1][2];
            weight[q - 1][2] = v * p;
            weight[q - 1][3] = weight[q - 1][1] + weight[q - 1][2];
        }
    }
    for (i = 0; i < m; i++)
    {
        for (int j = 1; j < 4; j++)
        {
            if (val[i][0] != 0&&val[i][j]!=0)
            {
                val[i][j] = val[i][j] + val[i][0];
                weight[i][j] = weight[i][j] + weight[i][0];
            }
        }
    }
    int n = N/10;
    int dp[3200] = { 0 };
  for (i = 0; i <m; i++)
    {
        if (val[i][0] == 0)
            continue;
        for (n = N / 10; n >= 0; n--)
        {
            for (j=0;j<4;j++)//（就是这里，如果把主件+附件当作单独的物品遍历，既遍历下标的循环在钱的外层，这种操作就是将主件，主件+附件1，主件+附件2，主件+附件1+附件2看作独立个体，出现重复计算，既n>主件+附件1的值时，会出现dp[n]=主件（weight[i][0]）+主件和附件1(weight[i][1])的情况。只有先遍历下标，实现覆盖操作既n给定，后遍历下标，才能做到不重复计算（如果理解有困难手推一遍既可）n=2000,m=3,10 4 0,10 4 1,10 4,1）
            {
                if(n>= val[i][j] / 10)
                dp[n] = max(dp[n], dp[n - val[i][j]/10] + weight[i][j]);
            }
        }
    }
    printf("%d\n", dp[N/10]);
    return 0;
}