C 语言 购物单问题

注意此代码默认，一件物品只能买一次
而输入顺序可以随机

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

int max(int a, int b){
    if(a>b)
        return a;
    else
        return b;
}

int main(void){
    int N,m; // N：钱，M总物品数
    scanf("%d %d",&N,&m);
    int x,y,z;
    int value[m][4];// 价钱与重要度乘积
    int cost[m][4];// 价钱，0：主；1、2：附
    memset(value, 0, m * 4 * sizeof(int));
    memset(cost, 0, m * 4 * sizeof(int));

    for(int i=0;i<m;i++){
        scanf("%d %d %d", &x, &y, &z);
        // 分主附件，转化01背包问题
        // 计算四种情况的value和cost
        if(z==0){
            value[i][0]=x*y;
            cost[i][0]=x;
        }
        else if(cost[z-1][1]==0){
            // 第z件为其主件，对应下标z-1
            cost[z-1][1]=x;
            value[z-1][1]+=x*y;
        }
        else{
            cost[z-1][2]=x;
            value[z-1][2]=x*y;
            cost[z-1][3] = cost[z-1][1]+cost[z-1][2];
            value[z-1][3] = value[z-1][1]+value[z-1][2];
        }
    }
    for(int i=0;i<m;i++){
        for(int k=1; k<4;k++){
            cost[i][k] += cost[i][0];
            value[i][k] += value[i][0];
        }
    }

//     for(int i=0; i<m; i++){
//         for(int k=0;k<4;k++)
//             printf("%d %d    ", cost[i][k], value[i][k]);
//         printf("\n");
//     }

    int dp[m+1][N+1];
    int max_v=0;
    memset(dp, 0, (m+1)*(N+1)*sizeof(int));
    // 可以考虑优化，0行略过
    for(int i=1; i<=m; i++){
        for(int j=10;j<=N;j+=10){
            max_v = dp[i-1][j];
            for(int k=0;k<4;k++){
                if(k>0 && cost[i-1][k]==cost[i-1][0])
                    break;
                if(j-cost[i-1][k]>=0)
                    max_v = max(max_v,dp[i-1][j-cost[i-1][k]]+value[i-1][k]);
            }
            dp[i][j] = max_v;
        }
    }
    printf("%d", dp[m][N]);
    return 0;
}