初学者学信息——信息学中的"一材多用"
tip
这次分享的方法对于已经完全会背包问题的人来说很麻烦,也很愚蠢。 仅供初学者记忆
引入
众所周知，AcWing首页前几题都是背包问题，而算法都是DP 其实，我素来只记住多重背包问题II，而其他问题却迎刃而解 首先，我们来看看多重背包问题II的代码： 题解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+100;
ll v[N],w[N];
ll f[N];
int main()
{
ll n,m;
ll cnt=1;
cin>>n>>m;
ll a,b,c;
for(ll i=1;i<=n;i++)
{
cin>>a>>b>>c;
ll k=1;
while(k<=c)
{
v[cnt]=a*k;
w[cnt]=b*k;
c-=k;
k*=2;
cnt++;
}//采用二进制优化
if(c!=0)
{
v[cnt]=a*c;
w[cnt]=b*c;
cnt++;
}//若用二进制优化后，仍然有余数，则在拿余数和之前的数，便可以表示1~c的所有整数
}
for(ll i=1;i<=cnt;i++)
{
for(ll j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);//01背包
}
}
cout<<f[m];
return 0;
}不难发现，我们可以将01背包换成数量为1的多重背包问题II来做 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+100;
ll v[N],w[N];
ll f[N];
int main()
{
ll n,m;
ll cnt=1;
cin>>n>>m;
ll a,b,c;
for(ll i=1;i<=n;i++)
{
cin>>a>>b;
c=1;//数量：1
ll k=1;
while(k<=c)
{
v[cnt]=a*k;
w[cnt]=b*k;
c-=k;
k*=2;
cnt++;
}//采用二进制优化
if(c!=0)
{
v[cnt]=a*c;
w[cnt]=b*c;
cnt++;
}//若用二进制优化后，仍然有余数，则在拿余数和之前的数，便可以表示1~c的所有整数
}
for(ll i=1;i<=cnt;i++)
{
for(ll j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);//01背包
}
}
cout<<f[m];
return 0;
}接下来是完全背包 由于总体积为m，每个物品的体积为v[i]，那么背包内最多可放入m/v[i]个物品（应该很好理解????） 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+100;
ll v[N],w[N];
ll f[N];
int main()
{
ll n,m;
ll cnt=1;
cin>>n>>m;
ll a,b,c;
for(ll i=1;i<=n;i++)
{
cin>>a>>b;
c=m/a;//数量：m/a（v[i]）
ll k=1;
while(k<=c)
{
v[cnt]=a*k;
w[cnt]=b*k;
c-=k;
k*=2;
cnt++;
}//采用二进制优化
if(c!=0)
{
v[cnt]=a*c;
w[cnt]=b*c;
cnt++;
}//若用二进制优化后，仍然有余数，则在拿余数和之前的数，便可以表示1~c的所有整数
}
for(ll i=1;i<=cnt;i++)
{
for(ll j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);//01背包
}
}
cout<<f[m];
return 0;
}然后多重背包问题I，完全可以直接使用多重背包问题II的代码
接着是多重背包问题III
tip
此代码附带卡常，比赛禁止使用！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
#include <iostream>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#pragma GCC optimize(5)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("Os")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll N=1e4*2+100;
ll n,m;
ll a,b,c;
ll f[N];
ll v[N],w[N];
ll cnt=1;
signed main()
{
cin>>n>>m;
for(ll i=1;i<=n;i++)
{
cin>>a>>b>>c;
ll k=1;
while(k<=c)
{
v[cnt]=k*a;
w[cnt]=k*b;
cnt++;
c-=k;
k*=2;
}
if(c!=0)
{
v[cnt]=c*a;
w[cnt]=c*b;
cnt++;
}
}
for(ll i=1;i<=cnt;i++)
{
for(ll j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m];
return 0;
}最后是我们的混合背包 数量只要按照判定好类型后加以改正即可
#include <bits/stdc++.h>
using namespace std;
int n,m,v[100010],w[100010],f[100010];
int main()
{
cin>>n>>m;
int cnt=1;
for(int i=1;i<=n;i++)
{
int a,b,s;
cin>>a>>b>>s;
int k=1;
if(s<0)s=1;
else if(s==0)s=m/a;//把01背包和多重背包先转化成多重背包，若为完全背包，则在最优情况下，只能取总体积/该物品体积向下取整
while(k<=s)
{
v[cnt]=a*k;
w[cnt]=b*k;
s-=k;
k*=2;
cnt++;
}
if(s>0)
{
v[cnt]=s*a;
w[cnt]=s*b;
cnt++;
}
}//将多重背包进行二进制优化，变成01背包
for(int i=1;i<=cnt;i++)
{
for(int j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}//01背包问题
cout<<f[m]<<endl;
return 0;
}