首页 > 其他分享 >0/1分数规划总结

0/1分数规划总结

时间:2024-03-02 19:45:23浏览次数:25  
标签:分数 总结 return int mid back front times 规划

前言

最近在搞什么树套树,博弈论,啥啥啥的,时间实在紧迫,就先拿 0/1 规划开刀。

0/1 分数规划是什么

实际上是一类问题。

顾名思义,0/1 即 对于 \(n\) 个物品,选择或者不选择。分数,即对于每个物体,有两个属性 \(a_i,b_i\),选出物品的价值就是 \(\dfrac{\sum a_i \times d_i}{\sum b_i \times d_i}\)。(\(d_i\) 表示第 \(i\) 个物体选没选)。规划,即对于其求一个最值,且需要保证选择了 \(k\) 个。

假设我们此时要求一个最大值。

显然,我们可以考虑一个二分,对于每一个物体,他的权值为 \(a_i-b_i \times mid\)。(\(mid\) 表示当前二分的答案)

可以通过以下恒等变形深入理解为何这样设权:

\[\begin{aligned} & \dfrac{\sum a_i \times d_i}{\sum b_i \times d_i} \ge mid \\ & \sum a_i \times d_i \ge mid \times \sum b_i \times d_i \\ & \sum a_i \times d_i - mid \times \sum b_i \times d_i \ge 0\\ & \sum (a_i-mid\times b_i) \times d_i \ge 0 \end{aligned} \]

非常容易想到,对于每个点的的权值从大到小排序,选择排完后的前 \(k\) 个,如果选出来的权值大于 \(0\),则返回 \(\text{true}\),否则 \(\text{false}\)。

于是,我们就有了一份版子题目的代码:

bool check(double mid)
{
	for (int i = 1; i <= n; ++i) c[i] = a[i] - mid * b[i];
	stable_sort(c + 1, c + n + 1);
	reverse(c + 1, c + n + 1);
	double now = 0;
	for (int i = 1; i <= k; ++i) now += c[i];
	return now >= 0;
}

对于同类型的题目,往往是将分数进行变形,或者有了更复杂的约束条件,但大致思想都是二分,难点往往都是如何去检查。

总的来说,这种题目还是比较具有套路性。

一些变形

\(\text{1.Talent show}\)

这道题目较于版子,多的限制是你要让 \(\sum b_i\times d_i \ge k\)。

非常容易想到一个背包,一个物体空间为 \(b_i\),价值为 \(a_i-mid\times b_i\)。但是由于你的限制不是刚好而是大于等于,所以你的背包需要做一些改进。

一个很好的解决方案是顺推,当你发现当前的重量加上新的物体重量大于等于 \(k\) 时,就把他看作 \(k\) 继续转移就行了。(因为你在 \(\ge k\) 的重量上继续选物品实际上和刚好选 \(k\) 的重量没有什么本质的区别。)

bool check(double mid)
{
	for (int i = 1; i <= n; ++i) c[i] = b[i] - mid * a[i];
	for (int i = 0; i <= n; ++i) for (int j = 0; j <= k; ++j) dp[i][j] = -1e9;
	dp[0][0] = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j <= k; ++j)
		{
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
			dp[i + 1][min(j + a[i + 1], k)] = max(dp[i + 1][min(j + a[i + 1], k)], dp[i][j] + c[i + 1]);
		}
	}
	return dp[n][k] >= 0;
}

\(\text{2.Best Group}\)

这题较上题的不同之处在于是在有约束条件下选 \(k\) 个得到分数的最大值。

所以考虑在树上背包。

定义 \(dp_{x,j}\) 表示已 \(x\) 为根的子树中,选择了 \(j\) 个。

  • 如果 \(x\) 不选,显然他的子树里面也没有一个可以选择,故 \(dp_{x,0}=0\)。

  • 如果选择 \(x\),则对于每个儿子 \(y\),枚举要在里面选择多少个,即 \(dp_{x,j}= \max \{dp_{x,j},dp_{y,k}+dp_{x,j - k}\}\)

最后看 \(dp_{0,k}\) 与 \(0\) 的大小关系即可。

至于时间复杂度,可以看这篇博客。

int dfs(int x)
{
//	cout << x << endl;
	for (int i = 0; i <= m + 1; ++i) dp[x][i] = -1000000000;
//	dp[x][0] = 0;
	if(x) dp[x][1] = 1.0 * fight[x] - cost[x] * MId;
	int now = 1;
	if(!x) dp[x][1] = 0;
	for (int i = fst[x]; i; i = arr[i].nxt)
	{
		int j = arr[i].tar, L;
		now += L = dfs(j);
		for (int k = min(now, m + 1); k >= 1; --k)
		{
			for (int l = 0; l <= min(k - 1, L); ++l)
			{
				dp[x][k] = max(dp[x][k - l] + dp[j][l], dp[x][k]);
			}
		}
	}
	return now;
} 
bool check(double mid)
{
	MId = mid;
	dfs(0);
	if(dp[0][m + 1] >= 0) return true;
	else return false;
}

\(\text{3.Smallest Circle}\)

题意即,在图中找一个环,使得环上边权之和除以节点个数最小,求这个最小平均值。

一样是先二分,将边权设为原来的减去 \(mid\),看能不能在图中找到负环,如果找到了,就返回真,否则假。(因为环上是 \(n\) 个点,\(n\) 条边,所以一条边就可以对应一个 \(mid\))

bool spfa(int st)
{
	vis[st] = true;
	for (int i = fst[st]; i; i = arr[i].nxt)
	{
		int j = arr[i].tar;
		double k = arr[i].num;
		if(dis[j] > dis[st] + k)
		{
			dis[j] = dis[st] + k;
			if(vis[j]) return true;
			if(spfa(j)) return true;
		}
	}
	vis[st] = false;
	return false;
}
bool check(double mid)
{
	for (int i = 1; i <= cnt; ++i) arr[i].num -= mid;
	for (int i = 1; i <= n; ++i) dis[i] = 0;
	memset(vis, 0, sizeof(vis));
	bool flg = 0;
	for (int i = 1; i <= n; ++i)
	{
		if(spfa(i))
		{
			flg = 1;
			break;
		}
	}
	for (int i = 1; i <= cnt; ++i) arr[i].num += mid;
	return flg;
}

\(\text{4.Send Gift}\)

题意很清楚,这里不阐述了。

首先有二分答案。

有一点非常显然,即我们总是希望最大最小值在端点处。因为如果不在端点处,那么必然可以缩小这个区间,使得限制没有那么苛刻。

我们可以枚举所有的右端点,然后用单调队列维护在左边的最优值(维护两次,一次最小,一次最大)

但这样还不够,我们还要同理的在维护一遍所有的左端点。

但有些时候,由于你的区间长度在一个范围之内,就会导致你无法做到最大最小全在端点处,所以还需要维护一下 \(\text{rmq}\),来计算答案。

int dp[100005][21][2];
void init()
{
	for (int i = 1; i <= n; ++i) dp[i][0][0] = dp[i][0][1] = a[i];
	for (int j = 1; (1 << j) <= n; ++j)
	{
		for (int i = 1; i + (1 << j) - 1 <= n; ++i)
		{
			dp[i][j][0] = min(dp[i][j - 1][0], dp[(i + (1 << j - 1))][j - 1][0]);
			dp[i][j][1] = max(dp[i][j - 1][1], dp[(i + (1 << j - 1))][j - 1][1]);
		}
	}
}
int rmq(int l, int r, int op)
{
	int k = __lg(r - l + 1);
	if(op) return max(dp[l][k][op], dp[r - (1 << k) + 1][k][op]);
	else return min(dp[l][k][op], dp[r - (1 << k) + 1][k][op]);
}
bool check(double mid)
{
	deque<int> p;
	for (int i = l; i <= n; ++i)
	{
		while(!p.empty() && i - p.front() + 1 > r) p.pop_front();
		while(!p.empty() && (a[p.back()] + (n - p.back()) * mid <= a[i - l + 1] + (n - (i - l + 1)) * mid)) p.pop_back();
		p.push_back(i - l + 1);
		if((rmq(p.front(), i, 1) - rmq(p.front(), i, 0)) >= (i - p.front() + m) * 1.0 * mid) return true;
	}
	while(!p.empty()) p.pop_back();
	for (int i = n - l + 1; i >= 1; --i)
	{
		while(!p.empty() && p.front() - i + 1 > r) p.pop_front();
		while(!p.empty() && (a[p.back()] + p.back() * mid <= a[i + l - 1] + (i + l - 1) * mid)) p.pop_back();
		p.push_back(i + l - 1);
		if(rmq(i, p.front(), 1) - rmq(i, p.front(), 0) >= (p.front() - i + m) * 1.0 * mid) return true;
	}
	while(!p.empty()) p.pop_back();
	for (int i = n - l + 1; i >= 1; --i)
	{
		while(!p.empty() && p.front() - i + 1 > r) p.pop_front();
		while(!p.empty() && (a[p.back()] + p.back() * mid >= a[i + l - 1] + (i + l - 1) * mid)) p.pop_back();
		p.push_back(i + l - 1);
		if(rmq(i, p.front(), 1) - rmq(i, p.front(), 0) >= (p.front() - i + m) * 1.0 * mid) return true;
	}
	while(!p.empty()) p.pop_back();
	for (int i = l; i <= n; ++i)
	{
		while(!p.empty() && i - p.front() + 1 > r) p.pop_front();
		while(!p.empty() && (a[p.back()] + (n - p.back()) * mid >= a[i - l + 1] + (n - (i - l + 1)) * mid)) p.pop_back();
		p.push_back(i - l + 1);
		if((rmq(p.front(), i, 1) - rmq(p.front(), i, 0)) >= (i - p.front() + m) * 1.0 * mid) return true;
	}
	return false;
}

后记

总的来说,这种题目本身并不难,难点往往是与其他知识点的迁移。

标签:分数,总结,return,int,mid,back,front,times,规划
From: https://www.cnblogs.com/SFsaltyfish/p/18049114

相关文章

  • 每日总结
    1.在java中,数组是一个对象,不是一种原生类,对象所以存放在堆中,又因为数组特性,是连续的。2.用户不能调用构造方法,只能通过new关键字自动调用。这句话是错误的。在类内部可以用户可以使用关键字this.构造方法名()调用(参数决定调用的是本类对应的构造方法)在子类中用户可以通过......
  • Linux_Centos_yum报错总结
    ​此篇适用于yum报错【尝试其他镜像】并且【curl外网】不通的情况,此时一般考虑是网络的问题一,出现的报错信息: 此时测试curl/pingwww.baidu.com会发现无法连通 二,解决方法:1,首先查看dns的配置文件/etc/resolv.conf检查这里的nameserver这里有时候会因为第二个网卡......
  • YL 模拟赛总结 15
    ProblemT1感觉是最难的。考虑贪心。首先对牛的按左端点进行排序,然后对于每只鸡去考虑匹配哪头牛。具体地,开一个小根堆,然后对于每只鸡\(t_i\),将\(a_i\let_i\)的牛放入堆中,此时堆中存放的是候选的牛。然后对于堆中的牛,将\(b_i<t_i\)的牛弹出。此时堆中的牛均是合法的......
  • YL 模拟赛总结 14
    Problem省流:三道题写了tjT1见tj。T2见tj。T3见tj。T4二分求出左右端点即可。#include<bits/stdc++.h>usingnamespacestd;intn,q;intp[200031];intmain(){//freopen("haybales.in","r",stdin);//freopen("haybales.out",&quo......
  • YL 模拟赛总结 13
    ProblemT1略。T2略。T3考虑对于每一头向北的牛,计算它能够挡住/被挡住几头向东的牛。一头向北的牛\(i\)能够被向东的牛\(j\)挡住的条件是:\(x_i<x_j\)且\(y_i<y_j\)(\(x_i,y_i\)分别表示牛\(i\)的\(x\)坐标与\(y\)坐标);\(l_j\)没有被更新(\(l_i\)表示第......
  • YL 模拟赛总结 12
    ProblemT1略。T2最理想的情况当然是奇偶交替,每个数单独成为一组。考虑不理想的情况:偶数个数\(>\)奇数个数,此时需要可以先奇偶交替,再将最后剩下的偶数单独分为一组,答案为奇数个数\(\times\2+1\)。奇数个数\(>\)偶数个数,此时再分出两种情况:若奇数个数\(-\)......
  • YL 模拟赛总结 10
    ProblemT1二分板子。对于\(c_i\)降序排序,然后二分\(h\)指数,在check中贪心地使用综述增加引用次数即可。T2通过观察可以发现,在一篇论文的贡献列表中,若某一位置出现了比它前面的名字的字典序更小的情况,则说明从这个位置开始,后面的人的资历一定\(\ge\)前面的人。根据......
  • YL 模拟赛总结 9
    ProblemT1我们考虑一种贪心策略:对于价格前\(n-1\)小的咖啡,我们求出一种最优方案使得按照此方案买完咖啡后钱数\(\ge20\)且最接近\(20\)。至于如何求出最优方案,进行一遍01背包即可。#include<bits/stdc++.h>usingnamespacestd;intn,k;inta[1031],dp[1031];i......
  • YL 模拟赛总结 6
    ProblemT1为了方便处理,我们令男生为\(1\),女生为\(-1\)。求一遍前缀和\(sum\),若存在两个下标\(l,r\)使得\(sum_l=sum_r\),则说明区间\([l+1,r]\)的和为\(0\),即男女人数相等。在这样的区间中取长度最大的即可。需要特殊处理\(sum_0\)。#include<bits/stdc++.h>#defi......
  • YL 模拟赛总结 7
    ProblemT1预处理出前\(10^4\)个格子需要填什么数,然后输出即可。具体地,我们记录\(e\)为当前层数,\(o\)为上一层的最后一个的位置,\(last\)为上一个填的格子的位置。我们知道,一个格子要么在一层的起点,要么在一层的中间,要么在一层的末尾。枚举\(1\sim5\)分别对这三种情......