01分數規畫
我們可以二分一個ans,然後化一下式子
一個總共有k個人的方案,要使(a[1]+a[2]+....+a[k])/(b[1]+b[2]+....+b[k])>=ans(a[1]+a[2]+....+a[k])/(b[1]+b[2]+....+b[k])>=ans(a[1]+a[2]+....+a[k])/(b[1]+b[2]+....+b[k])>=ans,當且僅當(a[1]−b[1]∗ans)+(a[2]−b[2]∗ans)+.....+(a[k]−b[k]∗ans)>=0(a[1]-b[1]*ans)+(a[2]-b[2]*ans)+.....+(a[k]-b[k]*ans)>=0(a[1]−b[1]∗ans)+(a[2]−b[2]∗ans)+.....+(a[k]−b[k]∗ans)>=0,由於這道題兒子選了父親必須選,於是將第i個物品權值變為(a[i]−b[i]∗ans)(a[i]-b[i]*ans)(a[i]−b[i]∗ans),進行背包dp即可,記f[x][i]f[x][i]f[x][i]表示x點選多少個人,枚舉選多少個人再dp,看f[0][k]f[0][k]f[0][k]是否>=0即可
#include<bits/stdc++.h>
using namespace std;
int k,n,h[2510],v[10010],nxt[10010],ec,sz[2510];
double s[2510],p[2510],f[2510][2510],c[2510];
void add(int x,int y){v[++ec]=y;nxt[ec]=h[x];h[x]=ec;}
void dfs(int x){
f[x][1]=c[x];
sz[x]=1;
for(int i=2;i<=k;i++)
f[x][i]=-1e9;
for(int i=h[x];i;i=nxt[i]){
dfs(v[i]);
sz[x]+=sz[v[i]];
for(int j=min(sz[x],k);j>=0;j--)
for(int l=0;l<=min(sz[v[i]],j-1);l++)
f[x][j]=max(f[x][j],f[v[i]][l]+f[x][j-l]);
}
}
int main(){
scanf("%d%d",&k,&n);k++;
for(int i=1;i<=n;i++){
int c;
scanf("%lf%lf%d",&p[i],&s[i],&c);
add(c,i);
}
double l=0,r=10000;
while(fabs(r-l)>1e-4){
double mid=(l+r)*0.5;
for(int i=1;i<=n;i++)
c[i]=s[i]-p[i]*mid;
dfs(0);
if(f[0][k]>=0)l=mid;
else r=mid;
}
printf("%.3lf",l);
}