混合背包¶
混合背包，就是将各种背包混合后的背包模型。
有 N 种物品和一个容量是 V 的背包。物品一共有三类，每种体积是 vi，价值是 wi。
第一类物品只能用1次（01背包）； 第二类物品可以用无限次（完全背包）； 第三类物品最多只能用 si 次（多重背包）；
上面三种情况其实都是完全背包，很好理解。
有些时候，混合背包还会和分组背包结合，具体可以看例题。
例题 #1¶
有N个物品，物品个数为Ai（Ai为0则无个数限制），价值为Wi，体积为Ci，给出G组限制，每组中的物品最多只能取一种，问物品体积刚好为D时，最大价值是多少
输入格式¶
第一行两个整数N和 D。 接下来N行，每行3个整数Ai，Wi，Ci 。 第N+2行一个非负整数 G 。 接下来G行，开头一个整数L，表示组的大小，然后L个整数，表示该组的物品编号，保证每个物品最多出现在一组中。
输出格式¶
输出一个整数表示最大的价值。若最大价值为负或无法满足体积恰好为V，则输出“i'm sorry...”。
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
// #define inr int
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s;
if(1)cerr<<' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
int f[N];
int vis[N];
vector<int> e[N];
int a[N],w[N],c[N];
void solve(){
int n=rd,v=rd;
for(int i=1;i<=n;i++){
a[i]=rd,w[i]=rd,c[i]=rd;
if(!a[i])a[i]=INF;
}
int q=rd;
for(int i=1;i<=q;i++){
int l=rd;
while(l--){
int a=rd;
e[i].push_back(a);
vis[a]=1;
}
}
for(int i=1;i<=n;i++){
if(vis[i])continue;
e[++q].push_back(i);//将为未分组的都独立分组
}
for(int i=0;i<N;i++)f[i]=-INF;
f[0]=0;
for(int i=1;i<=q;i++){
for(int j=v;j;j--){
for(auto k:e[i]){
//对于每一组都独立考虑
for(int l=1;l<=a[k]&&l*c[k]<=j;l++){
if(f[j-l*c[k]]==-INF)continue;
f[j]=max(f[j],f[j-l*c[k]]+l*w[k]);
}
}
}
}
if(f[v]==-INF)cout<<"i'm sorry..."<<endl;
else cout<<f[v]<<endl;
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}
例题 #2 旅行商的背包¶
小 S 坚信任何问题都可以在多项式时间内解决，于是他准备亲自去当一回旅行商。在出发之前，他购进了一些物品。这些物品共有 \(n\) 种，第 \(i\) 种体积为 \(V_i\)，价值为 \(W_i\)，共有 \(D_i\) 件。他的背包体积是 \(C\)。怎样装才能获得尽量多的收益呢？作为一名大神犇，他轻而易举的解决了这个问题。
然而，就在他出发前，他又收到了一批奇货。这些货共有 \(m\) 件，第 \(i\) 件的价值 \(Y_i\) 与分配的体积 \(X_i\) 之间的关系为：\(Y_i=a_iX_i^2+b_iX_i+c_i\)。这是件好事，但小 S 却不知道怎么处理了，于是他找到了一位超级神犇（也就是你），请你帮他解决这个问题。
输入格式
第一行三个数 \(n,m,C\)，如题中所述；
以下 \(n\) 行，每行有三个数 \(V_i,W_i,D_i\)，如题中所述；
以下 \(m\) 行，每行有三个数 \(a_i,b_i,c_i\)，如题中所述。
输出格式
仅一行，为最大的价值。
对于 \(100\%\) 的数据，\(1 \le n \le 10^4\)，\(1 \le m \le 5\)，\(1 \le C \le 10^4\)，$ 1 \le W_i,V_i,D_i \le 1000\(，\)-1000 \le a_i,b_i,c_i \le 1000$。
考虑前面的多重背包使用二进制拆分，后面的完全背包因为完全不符合**背包物品的可加性**，所以只能暴力枚举。
要勤于计算时间复杂度。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define itn int
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pf first
#define ps second
#define cdbg(x) cerr<<#x<<" = "<<x<<' ';
#define rd read()
inline int read(){
int x;
cin>>x;
return x;
}
const int N=5e5+5;
const int INF=1e18;
const int MOD=998244353;
/*
策略
主要来解决奇货问题
发现不适用于加法的法则了
即对于同一组abc
a(x+y)2+b(x+y)+c=
ax2+ay2+bx+by+c+2axy
所以不可以二进制分组
那么就直接枚举加多少呗！
但是未来减少枚举量，我们先把常规的背包做出来，再把这些加进去
*/
struct node{
int v,w;
}t[N];
int tot;
int f[N];
void solve(){
int n=rd,m=rd,c=rd;
for(int i=1;i<=n;i++){
int v=rd,w=rd,d=rd;
int k=1;
while(d>=k){
t[++tot]={v*k,w*k};
d-=k;
k<<=1;
}
if(d)t[++tot]={v*d,w*d};
}
for(int i=1;i<=tot;i++){
for(int j=c;j;j--){
if(j-t[i].v>=0)f[j]=max(f[j],f[j-t[i].v]+t[i].w);
}
}
// cdbg("OK");
//先求出一部分
for(int i=1;i<=m;i++){
int a=rd,b=rd,cc=rd;
for(int j=c;j;j--){
for(int k=0;k<=j;k++){
f[j]=max(f[j],f[j-k]+a*k*k+b*k+cc);
}
}
}
cout<<f[c]<<endl;
}
signed main(){
int T=1;
while(T--){
solve();
// if(T)puts("");
}
return 0;
}