动态规划 购物单

#include <stdio.h>

int max_value(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int N, m;
    scanf("%d %d", &N, &m);
    N = N / 10; //10的倍数
    int price[m][4];
    int value[m][4];//价值= 价值*满意度
    memset(price, 0, sizeof(price));
    memset(value, 0, sizeof(value));
    int v, p, q;
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &v, &p, &q);
        v = v / 10;
        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 { //附件2
            price[q - 1][2] = v;
            value[q - 1][2] = v * p;

            //有附件2就说明有附件1 附件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]; //m个物品 N的钱
    memset(dp, 0, sizeof(dp));
    int maxvalue = 0;
    for (int i = 1;i<m+1;i++){ //m件物品
        for(int j=1;j<N+1;j++){ //N金额
            maxvalue = dp[i-1][j];
            for(int k=0;k<4;k++){ //每件物品4种组合方式
                if(k>0 && price[i-1][k] == price[i-1][0]){ //没有附件
                    break;
                }
                if(j-price[i-1][k]>=0){//剩余奖金足够
                   maxvalue =  max_value(maxvalue, dp[i-1][j-price[i-1][k]] + value[i-1][k]);
                }
            }
            dp[i][j]=maxvalue;
        }
    }
    printf("%d",dp[m][N]*10);
        return 0;
}