题解：UVA12420 Item-Based Recommendation

furina_yyds · 2025-01-13 14:24:58 · 题解

题意

根据一些用户给一些电影的评价，计算出电影之间的“相似度”，随后通过相似度给一个人推荐电影。

思路

公式、计算方式、格式已在 PDF 中给出，模拟即可。

注意

• 在计算相似度时，如果两个并没有匹配，则相似度为 0。
• 在加权平均的分母为 0 的时候，注意不可以直接舍弃，而是作为 -nan (Not a Number) 进行排序和输出。

代码

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdio>
const int maxn = 210;
const double eps = 1e-6;
struct Recommendation {
    int index;
    double value;
};
bool cmp(const Recommendation& a, const Recommendation& b) {
    return a.value > b.value;
}
int main() {
    int n, m, c;
    std::cin >> n >> m >> c;
    double f[maxn][maxn] = {0.0};
    while (c--) {
        int u, v;
        double w;
        std::cin >> u >> v >> w;
        f[u][v] = w;
    }
    double s[maxn][maxn] = {0.0};
    for (int i = 1; i <= m; ++i) {
        for (int j = i; j <= m; ++j) {
            double sum = 0;
            for (int k = 1; k <= n; ++k) {
                if (f[k][i] > eps && f[k][j] > eps) {
                    sum += std::pow(f[k][i] - f[k][j], 2);
                }
            }
            s[i][j] = s[j][i] = 1.0 / (1.0 + sum);
        }
    }

    int q;
    while (std::cin >> q) {
        std::vector<Recommendation> v;
        for (int i = 1; i <= m; ++i) {
            if (f[q][i] < eps) {
                double dp = 0, dq = 0;
                for (int j = 1; j <= m; ++j) {
                    if (f[q][j] > eps) {
                        dp += s[i][j] * f[q][j];
                        dq += s[i][j];
                    }
                }
                if (dq > eps) {
                    Recommendation rec;
                    rec.index = i;
                    rec.value = dp / dq;
                    v.push_back(rec);
                }
            }
        }
        std::sort(v.begin(), v.end(), cmp);
        int s = v.size();
        s = std::min(s, 10);
        std::cout << "Recommendations for user " << q << ":\n";
        for (int i = 0; i < s; ++i) {
            std::cout << v[i].index << " " << std::fixed << std::setprecision(3) << v[i].value << "\n";
        }
        std::cout << "\n";
    }
    return 0;
}