HJ16 购物单

题目描述

王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的。

如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。

每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。

王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。

满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第i件物品的价格为v[i]，重要度为w[i]，共选中了k件物品，编号依次为j1,j2,…,jk，则满意度为：v[j1] x w[j1] + v[j2] x w[j2] + … + v[jk] x w[jk]。

请你帮助王强计算可获得的最大的满意度。

示例

输入：

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

输出：

2200

思路

如果没有主件附件的概念，那么基于“每件物品只能购买一次”这一点，此问题是一个裸的01背包问题。（只不过01背包模板问题里价值直接给出，这里给出的是重要程度，用它乘上价格才是价值。~~相当于在全裸的基础上穿了双袜子的程度~~）

Code(fake)

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
int v[65], p[65], q[65];
int ans[32005];

void solve() {
    memset(ans, 0, sizeof(ans));
    for(int i = 1; i <= m; ++i) {
        for(int j = n; j >= v[i]; --j) {
            ans[j] = max(ans[j], ans[ j - v[i] ] + v[i] * p[i]);
        }
    }
    cout << ans[n] << '\n';
    return ;
}

int main() {
    while (cin >> n >> m)
    {
        memset(v, 0, sizeof(v));
        memset(p, 0, sizeof(p));
        memset(q, 0, sizeof(q));
        for(int i = 1; i <= m; ++i) {
            scanf("%d%d%d", &v[i], &p[i], &q[i]);
        }
        solve();
    }
    return 0;
}

Code(Real)

这题卡了我一天……我一直把附件跟主件平等看待，认为他们是并列关系，秉着这一理念越做越乱，越做越复杂。

后来看了题解，题目描述里有这样一句话：“每个主件可以有 0 个、 1 个或 2 个附件”，也就是说每个主件的附件是有限的，最多俩，因此可以把附件看做主件的一部分，在考虑第 i 个主件是否放入背包时，有以下几种方案：

不放入主件
只放入主件
放入主件 + 附件1（若有）
放入主件 + 附件2（若有）
放入主件 + 附件1 （若有）+ 附件2（若有）

只遍历主件，从上述5种情况中取最大值即可

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
int v[65], p[65], q[65];
int f1[65], f2[65];
int ans[32005];

/*
a: 不放该主件
b: 只放入该主件
c: 放入主件 + 附件1
d: 放入主件 + 附件2
e: 放入主件 + 附件1 + 附件2
*/

void solve() {
    memset(ans, 0, sizeof(ans));
    for(int i = 1; i <= m; ++i) {
        //只遍历主件，把附件看做主件的一部分
        //从字面上也看得出来是主从关系，不是平等并列关系
        //所以我一开始的思路（平等看待主件与附件）就是错的
        if(q[i] == 0) {
            for(int j = n; j >= v[i]; --j) {
                int a = ans[j];
                int b = ans[ j - v[i] ] + v[i] * p[i];
                int c = 0, d = 0, e = 0;
                if(f1[i] && j >= (v[i] + v[ f1[i] ]))
                    c = ans[ j - v[i] - v[ f1[i] ] ] + v[i] * p[i] + v[ f1[i] ] * p[ f1[i] ];
                if(f2[i] && j >= (v[i] + v[ f2[i] ]))
                    d = ans[ j - v[i] - v[ f2[i] ] ] + v[i] * p[i] + v[ f2[i] ] * p[ f2[i] ];
                if(f1[i] && f2[i] && j >= (v[i] + v[ f1[i] ] + v[ f2[i] ]))
                    e = ans[ j - v[i] - v[ f1[i] ] - v[ f2[i] ] ] 
                        + v[i] * p[i] + v[ f1[i] ] * p[ f1[i] ] + v[ f2[i] ] * p[ f2[i] ];
                ans[j] = max(a, max(b, max(c, max(d, e))));
            }
        }
    }
    cout << ans[n] << '\n';
    return ;
}

int main() {
    freopen("00input.txt", "r", stdin);

    while (cin >> n >> m)
    {
        memset(v, 0, sizeof(v));
        memset(p, 0, sizeof(p));
        memset(q, 0, sizeof(q));
        memset(f1, 0, sizeof(f1));
        memset(f2, 0, sizeof(f2));
        for(int i = 1; i <= m; ++i) {
            scanf("%d%d%d", &v[i], &p[i], &q[i]);
            if(q[i] > 0) {
                int to = q[i];
                if(f1[to] > 0) f2[to] = i;
                else f1[to] = i;
            }
        }
        solve();
    }
    return 0;
}