【十二题解】 | #购物单#

主要就是要把该问题转化为01背包问题，因为每个物品最多购买一次，所以把主件，主件+附件1，主件+附件2，主件+附件1+附件2单独拿出来讨论

第二就是遍历顺序问题，普通的01背包就是直接先物品后容量，容量逆序遍历就行了，但是这个题因为我们把哪几种情况合体了，所以还有一个下标参数，这里必须是第二个进行遍历，也就是先物品，再下标，再容量（钱），否则就会一个物品相加多次，因为比如虽然主件+附件1我们是单独拿出来的，但是其实它里面是包含的有主件的，所以如果先把下边遍历了就会造成某些物品加了多次的情况

#include<stdio.h>

#include<stdlib.h>

int fmax(int a, int b) {

return a > b ? a : b;

} int main() {

int money_all;
int number;
scanf("%d %d", &money_all, &number);
int* val = (int*)malloc(sizeof(int) * number);
memset(val, 0, sizeof(int) * number);
int* imp = (int*)malloc(sizeof(int) * number);
memset(imp, 0, sizeof(int) * number);
int* sub = (int*)malloc(sizeof(int) * number);
memset(sub, 0, sizeof(int) * number);
int i;
for (int i = 0; i < number; i++) {
    scanf("%d %d %d", &val[i], &imp[i], &sub[i]);
}
int** cost = (int**)malloc(sizeof(int*) * number);
for (i = 0; i < number; i++) {
    cost[i] = (int*)malloc(sizeof(int) * 4);
    memset(cost[i], 0, sizeof(int)*4);
}
int** value = (int**)malloc(sizeof(int*) * number);
for (i = 0; i < number; i++) {
    value[i] = (int*)malloc(sizeof(int) * 4);
    memset(value[i], 0, sizeof(int)*4);
}
for (int i = 0; i < number; i++) {
    if (sub[i]==0) {
        cost[i][0] = val[i];
        value[i][0] = val[i] * imp[i];
    }
    else if (cost[sub[i] - 1][1] == 0) {
        cost[sub[i] - 1][1] = val[sub[i] - 1] + val[i];
        value[sub[i] - 1][1] = val[sub[i] - 1] * imp[sub[i] - 1] + val[i] * imp[i];
    }
    else {
        cost[sub[i] - 1][2] = val[sub[i] - 1] + val[i];
        value[sub[i] - 1][2] = val[sub[i] - 1] * imp[sub[i]-1] + val[i] * imp[i];
        cost[sub[i] - 1][3] = cost[sub[i] - 1][1] + cost[sub[i] - 1][2]- val[sub[i] - 1];
        value[sub[i] - 1][3] = value[sub[i] - 1][1] + value[sub[i] - 1][2]- val[sub[i] - 1] * imp[sub[i] - 1];
    }
}
free(val);
free(imp);
free(sub);
int* dp = (int*)malloc(sizeof(int) * money_all/10 + 1);
memset(dp, 0, sizeof(int) * money_all/10 + 1);
int money, thing, submit;
for (thing = 0; thing < number; thing++) {
    if (cost[thing][0] == 0)continue;
    for (money = money_all; money > 0; money -= 10) {
        for (submit = 0; submit < 4; submit++) {
            if (money >= cost[thing][submit]) {
                dp[money / 10] = fmax(dp[money / 10], dp[(money - cost[thing][submit]) / 10] + value[thing][submit]);
            }
            else {
                dp[money / 10] = dp[money / 10];
            }
        }
    }
}
printf("%d", dp[money_all/10]);

}