以下是一个用 unordered_map 实现的 01 背包，数据范围 $1\le n\le 300$。值域是 $10^9$。求分析时间复杂度。

mp[a[1].num]=a[1].w;
for(int i=2;i<=n;i++)
{
	for(auto it: mp)
	{
		int g=__gcd(it.first,a[i].num);
		if(!mp.count(g)) mp[g]=a[i].w+it.second;
		else mp[g]=min(mp[g],a[i].w+it.second);
	}
	if(!mp.count(a[i].num)) mp[a[i].num]=a[i].w;
	else mp[a[i].num]=min(a[i].w,mp[a[i].num]);
}
printf("%d\n",mp[1]);