动态规划-购物单

题目地址：https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4?tpId=37&tags=&title=&difficulty=0&judgeStatus=0&rp=1
完整代码：

#include <stdio.h>
#include <stdlib.h>

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

int main(int argc, char *argv[])
{
    int max=0, num=0;
    scanf("%d %d", &max, &num);
    max /= 10;  //因为价格都是10的整数倍，整体除10，减少空间占用和计算次数
    
    int v=0,p=0,q=0;
    int V[61][3];  //记录价格，最多1主2付，三维度数组
    int P[61][3];  //记录重要度
    int DP[max+1];
    memset(V, 0, sizeof(V));
    memset(P, 0, sizeof(P));
    memset(DP, 0, sizeof(DP));
    //将数据处理到 二位数组中
    for(int i=1; i<=num; i++) {
        scanf("%d %d %d", &v, &p, &q);
        v /= 10;
        if (q == 0) {
            V[i][0] = v;
            P[i][0] = v*p*10;
        } else {
            if (V[q][1] == 0) {
                V[q][1] = v;
                P[q][1] = v*p*10;
            } else {
                V[q][2] = v;
                P[q][2] = v*p*10;
            }
        }
    }
    
    for(int i=1; i<=num; i++) {
        for(int n=max; n>=V[i][0]; n--) {
            //只有主
            int sum = V[i][0];
            int all = P[i][0];
            DP[n] = MAX(DP[n], DP[n-sum]+all);
            
            //如果有付1 主+付1
            if (V[i][1] > 0) {
                sum = V[i][0] + V[i][1];
                all = P[i][0] + P[i][1];
                if (n >= sum) {
                    DP[n] = MAX(DP[n], DP[n-sum]+all);
                }
            }
            
            //如果有付2 
            if (V[i][2] > 0) {
                //主+付2
                sum = V[i][0] + V[i][2];
                all = P[i][0] + P[i][2];
                if (n >= sum) {
                    DP[n] = MAX(DP[n], DP[n-sum]+all);
                }
                //主+付1+付2
                sum = V[i][0] + V[i][1] + V[i][2];
                all = P[i][0] + P[i][1] + P[i][2];
                if (n >= sum) {
                    DP[n] = MAX(DP[n], DP[n-sum]+all);
                }
            }
        }
    }
    printf("%d", DP[max]);
    
    return 0;
}