引入

分數規劃主要是對形如
$$\frac{\sum _{i=1}^n{a}_i?w_i}{\sum _{i=1}^n{b}_i?w_i}$$
\(w\)數組表示選與不選，最值化上式，不過一般會要求選k個，或者總重量至少為\(W\)再加上一大堆亂七八糟的限制
——————————————————————

解決方法

一般來講用二分法，還有一個\(Dinkelbach\) 算法算是對二分的優化，就是用上一次的答案來做左邊界，不過我們沒有必要學習它

P10505
在這可以寫一下分數規劃的基本原理
\(\frac{a}{b}>mid\Longrightarrow a-b*mid>0\)
找所有大于0的元素對累加即可
基本上所有的分數規劃都是這個原理，而這個題讓我們選擇\(n-k\)個數，如果必須要選擇負數那怎么辦呢，考慮此時還滿足相加嗎，實際上是滿足的（在\(mid<1\)時），讀者感興趣可以自己去證明

那這題式子很顯然就是\(設 t_i=a_i-mid*b_i,取最大的幾個即可\)

P4377

這就是我說的那種總重量至少為\(W\)的題，也不算惡心，\(check\)里面改成背包，注意這題的重量加和可能會很大，所以\(f_i\)定義為重量和至少為\(i\)的最優值,填表寫感覺更好捏

bool check(double x) {
	for(int i=1;i<=w;i++) f[i]=-P;
	for(int i=1;i<=n;i++) {
		t[i]=a[i]-b[i]*1.0*x;
		for(int j=w;j>=0;j--) 
			if(j+b[i]<=w)
				f[j+b[i]]=max(f[j+b[i]],f[j]+t[i]);
			else 
				f[w]=max(f[w],f[j]+t[i]);
	}
//	for(int i=w;i<=W;i++) if(f[i]>0) return 1;
	return f[w]>=0.0;
}

\(P4322 [JSOI2016]最佳團體\)

可以發現這是一個樹的結構，考慮樹上背包，\(f_{i,j}\)表示在i的子樹中選j個，會發現這個式子看起來像\(O(n^3)\)的，但其實是\(O(n^2)\)的，可以參考這篇博客 this

給你們看一下小代碼

void dfs(int p) {
	t[p]=a[p]-b[p]*mid;
	int tot=0;
	for(int i=1;i<=siz[p];i++) f[p][i]=-P;
	for(auto i:v[p]) {
		dfs(i);
		for(int j=0;j<=tot;j++) {
			for(int k=1;k<=siz[i];k++) {
				f[p][j+k]=max(f[p][j+k],f[p][j]+f[i][k-1]+t[i]);
			}
		}
		tot+=siz[i];
	}
}

$「SDOI2017」新生舞會 $