背包DP

背包DP

二进制分组优化

考虑优化。我们仍考虑把多重背包转化成 0-1 背包模型来求解。

预处理物品数量是2的次方。且要覆盖物品数量的点。即2 n次方+1到k

index = 0;
for (int i = 1; i <= m; i++) {
  int c = 1, p, h, k;
  cin >> p >> h >> k;
  while (k > c) {
    k -= c;
    list[++index].w = c * p;
    list[index].v = c * h;
    c *= 2;
  }
  list[++index].w = p * k;
  list[index].v = h * k;
}

单调队列优化背包

求区间为m中的最小值

t=1;
	for (i=1;i<=n;i++)
	{
		if ((b[t]<i-m+1)and(t<=w))
			t++;
		while ((t<=w)and(a[b[w]]>=a[i]))
			w--;
		w++;
		b[w]=i;
		if (i>=m)
			cout<<a[b[t]]<<' ';
	}

单调队列求连续子序列最大和

子序列最大长度为m

for (i=1;i<=n;i++)
	{
		cin>>x;
		a[i]=a[i-1]+x;
	}
	ma=a[1];
	for (i=1;i<=n;i++)
	{
		if ((b[t]<i-m+1)and(t<=w))
			t++;
		ma=max(ma,a[i]-a[b[t]]);
		while ((t<=w)and(a[b[w]]>=a[i]))
			w--;
		w++;
		b[w]=i;
	}
	cout<<ma<<'\n';

单调队列优化多重背包

	cin>>n>>m;
	for (i=1;i<=n;i++)
	{
		cin>>v>>z>>k;             //价值 重量 数量
		for (j=0;j<=z-1;j++)
		{
			t=0;w=0;
			o=(m-j)/z;
			for (l=0;l<=o;l++)
			{
				while ((t<w)and(f[j+l*z]-l*v>=c[w-1]))
					w--;
				b[w]=l;
				c[w]=f[j+l*z]-l*v;
				w++;
				while ((t<w)and(b[t]<l-k))
					t++;
				f[j+l*z]=max(f[j+l*z],c[t]+l*v);
			}
		}
	}
	cout<<f[m];

有依赖的背包

金明的预算方案 洛谷1064

#include<bits/stdc++.h>
using namespace std;
int n,m,i,x,q,t,k,j,l,z,vv,pp,f[400005],v[40005],p[40005],a[40005];
vector<int>b[40005];
int main()
{
	cin>>m>>n;
	for (i=1;i<=n;i++)
	{
		cin>>v[i]>>p[i]>>x;
		p[i]=p[i]*v[i];
		if (x==0)
			a[++k]=i;
		else
			b[x].push_back(i);
	}
	for (i=1;i<=k;i++)
	{
		q=a[i];
		t=b[q].size();
		for (l=m;l>=v[q];l--)
		{
			for (j=0;j<=(1<<t)-1;j++)
			{
				vv=v[q];pp=p[q];
				for (z=0;z<b[q].size();z++)
					if ((1<<z)&j)
					{
						vv=vv+v[b[q][z]];
						pp=pp+p[b[q][z]];
					}
				if (l>=vv)
					f[l]=max(f[l],f[l-vv]+pp);
			}
		}
	}
	cout<<f[m]<<'\n';
}

01背包的第K优解

memset(dp, 0, sizeof(dp));
int i, j, p, x, y, z;
scanf("%d%d%d", &n, &m, &K);
for (i = 0; i < n; i++) scanf("%d", &w[i]);
for (i = 0; i < n; i++) scanf("%d", &c[i]);
for (i = 0; i < n; i++) {
  for (j = m; j >= c[i]; j--) {
    for (p = 1; p <= K; p++) {
      a[p] = dp[j - c[i]][p] + w[i];
      b[p] = dp[j][p];
    }
    a[p] = b[p] = -1;
    x = y = z = 1;
    while (z <= K && (a[x] != -1 || b[y] != -1)) {
      if (a[x] > b[y])
        dp[j][z] = a[x++];
      else
        dp[j][z] = b[y++];
      if (dp[j][z] != dp[j][z - 1]) z++;          //策略不同但权值相同的看作重复的就加这句
    }
  }
}
printf("%d\n", dp[m][K]);

多人背包 洛谷1858

#include<bits/stdc++.h>
using namespace std;
int k,n,m,i,j,p,x,y,s,t,w,z,f[5005][55],a[55],b[55];
int main()
{
	cin>>k>>m>>n;
	for (i=0;i<=m;i++)
		for (j=1;j<=k;j++)
			f[i][j]=-1000000000;
	f[0][1]=0;
	for (i=1;i<=n;i++)
	{
		cin>>x>>y;
		for (j=m;j>=x;j--)
		{
			for (p=1;p<=k;p++)
			{
				a[p]=f[j-x][p]+y;
				b[p]=f[j][p];
			}
			t=w=z=1;
			while (((t<=k)or(w<=k))and(z<=k))
			{
				if (a[t]>b[w])
					f[j][z]=a[t++];
				else f[j][z]=b[w++];
				z++;
			}
		}
	}
	for (i=1;i<=k;i++)
		s+=f[m][i];
	cout<<s<<'\n';
}