题解 | #购物单#

本题的关键是将购物车问题转化为0-1背包问题，购物车的物品有主件和附件之分，而背包的物品没有这个限制，通过将附件物品转化为主件物品的状态，减少了物品数，增加了购买决策时的判断。

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

#define MAX(a,b) ((a>b)?a:b)
#define STATUS 4
/*
There are four statuses when we decide to buy one product.
First status: only buy it
Second status: buy it and its first accessory
Third status: buy it and its second accessory
Four status: buy it, first accessory and second accessory
So, we should decide which status is most valuable.
*/
int main(int argc, char* argv[]){
    int N,m;
    scanf("%d %d",&N,&m);
    N /= 10; //all prices are all multiples of 10
    
    int value[m][STATUS];
    int cost[m][STATUS];
    memset(value, 0, sizeof(value));
    memset(cost, 0, sizeof(value));
    
    int v, p, q;
    for(int i=0; i<m;i++){
        scanf("%d %d %d\n",&v, &p, &q);
        v /= 10; //all prices are all multiples of 10
        if(q == 0){
            //status1: master product
            value[i][0] = v * p;
            cost[i][0] = v;
        }
        else if(cost[q-1][1] == 0){
            //status2: first accessory
            cost[q-1][1] = v;
            value[q-1][1] = v*p;
        }
        else{
            //status3: second accessory
            cost[q-1][2] = v;
            value[q-1][2] = v*p;
            //status4: first accessory + second accessory
            cost[q-1][3] = cost[q-1][1] + v;
            value[q-1][3] = value[q-1][1] + v*p;
        }
    }
    
    //add the cost and value of master to status2,3,4
    for(int i=0; i<m; i++){
        for(int j=1; j<STATUS; j++){
            cost[i][j] = cost[i][0] + cost[i][j];
            value[i][j] = value[i][0] + value[i][j];
        }
    }
    
    // so makes m products to n products (n <= m) 
    // the serial number of products isn't changed
    // if serial number i is a accessory, value[i][0] = 0, cost[i][0] = 0
    
    int dp[m+1][N+1];
    memset(dp, 0, sizeof(dp));
    
    int max_value = 0;
    for(int i=1; i<=m; i++){
        for(int j=1; j<=N; j++){
            max_value = dp[i-1][j];
            for(int k =0; k<STATUS; k++)
            {
                if(cost[i-1][0] == 0){
                    // this serial number i-1 is a accessory
                    break;
                }
                else if(j < cost[i-1][0]){
                    // don't have enough money
                    break;
                }
                else if(k > 0 && cost[i-1][0] == cost[i-1][k]){
                    // don't have accessory
                    break;
                }
                else if(j >= cost[i-1][k]){
                    max_value = MAX(max_value,
                                    dp[i-1][j-cost[i-1][k]] + value[i-1][k]);
                }
            }
            
            dp[i][j] = max_value;
        }
    }
    
    printf("%d\n", dp[m][N] * 10);
    
    return 0;
}