栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

哈希算法题(砝码&数量得到种数)

C/C++/C# 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

哈希算法题(砝码&数量得到种数)

    现有n种砝码,重量互不相等,分别为 m1,m2,m3…mn ;

每种砝码对应的数量为 x1,x2,x3…xn 。现在要用这些砝码去称物体的重量(放在同一侧),问能称出多少种不同的重量。
注:
称重重量包括 0

#include 
#include 
#include 
#include 
using namespace std;

const int N = 15, M = 2010;
int n, m;
int w[N], v[N];

int main() {
    cin >> n;
    for(int i=1; i<=n; i++) cin >> v[i];
    for(int i=1; i<=n; i++) cin >> w[i];
    
    unordered_set S = {0};
    for(int i=1; i<=n; i++) {
        unordered_set tmp;
        for(auto &c : S) {
            for(int j=0; j<=w[i]; j++) {
                tmp.insert(c + j * v[i]);
            }
        }
        S = tmp;
    }
    
    cout << S.size() << endl;
    return 0;
}

输入:
4
1 2 3 4
2 1 4 5

输出:41

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/924032.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号