特殊背包¶
二维背包¶
二维背包（二维01背包）就是在原01背包左右一个限制——重量的基础上，再添加一个限制——体积。
给定n nn种物品和一背包。物品i ii的重量是w_i，体积是b_i，其价值为v_i，背包的容量为c cc，容积为d dd。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？
这时我们就需要在原有dp状态的基础上增加第3个维度。
设计dp状态为f_{i,j,k}表示可选物品为i,i+1,…,n；背包容量为j，背包容积为k时的二维01背包问题的最优值。在转移时延用01背包的转移方法，只不过需要判断两个条件。时间复杂度为O(nVM)。
优化上延用01背包优化方法，可以将第一维压去。
高维背包¶
高维背包并不是以多出限制的形式呈现，而是对多个物品由不同的数量限制。并且不同物品的数量通常≤5，这样我们可以在dp数组的每一个维度记录这个物品当前的数量
例题 #1 [USACO3.3] 商店购物 Shopping Offers¶
促销活动把一个或多个商品组合起来降价销售，例如：
三朵花的价格是 \(5\) 而不是 \(6\) ，\(2\) 个花瓶和一朵花的价格是 \(10\) 而不是 \(12\) 。 请编写一个程序，计算顾客购买一定商品的花费，尽量地利用优惠使花费最少。尽管有时候添加其他商品可以获得更少的花费，但是你不能这么做。
对于上面的商品信息，购买三朵花和两个花瓶的最少花费的方案是：以优惠价购买两个花瓶和一朵花（\(10\)），以原价购买两朵花（\(4\)）。
输入格式
输入文件包括一些商店提供的优惠信息，接着是购物清单。（最多有 \(5\) 种商品）
第一行 优惠方案的种类数（\(0\leq s\leq99\)）。
第 \(2\) 行 \(\sim\) 第 \(s+1\) 行 每一行都用几个整数来表示一种优惠方式。第一个整数 \(n\) （\(\leq n\leq5\)），表示这种优惠方式由 \(n\) 种商品组成。后面 \(n\) 对整数 \(c\) 和 \(k\) 表示 \(k\) （\(1\leq k\leq5\)）个编号为 \(c\) （\(1\leq c\leq999\)）的商品共同构成这种优惠，最后的整数 \(p\) 表示这种优惠的优惠价（\(1\leq p\leq9,999\)）。优惠价总是比原价低。
第 \(s+2\) 行 这一行有一个整数 \(b\) （\(0\leq b\leq5\)），表示需要购买 \(b\) 种不同的商品。
第 \(s+3\) 行 \(\sim\) 第 \(s+b+2\) 行 这 \(b\) 行中的每一行包括三个整数：\(c,k,p\) 。 \(c\) 表示唯一的商品编号（\(1\leq c\leq999\)），\(k\) 表示需要购买的 \(c\) 商品的数量（\(1\leq k\leq5\)）。\(p\) 表示 \(c\) 商品的原价（\(1\leq p\leq999\)）。最多购买 \(5\times5=25\) 个商品。
输出格式
只有一行，输出一个整数：购买这些物品的最低价格。
#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<<'\n';
#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;
/*
策略
记录f_{q,w,e,r,t}表示买了5种商品的数目为 qwert时最小代价。把清单和商品都看作物品即可。
*/
int f[7][7][7][7][7];
int p[7],pp[7];
int ans=INF;
int id[N];
int amt[7];
int orp[7];
int b;
itn n;
vector<pii > e[120];
int v[N];
bool check(int x){
for(int i=1;i<=b;i++){
pp[i]=p[i];
}
for(auto v:e[x]){
pp[v.pf]-=v.ps;
if(pp[v.pf]<0)return 0;
}
return 1;
}
void dfs(int x){
if(!x){
for(int i=1;i<=n;i++){
if(check(i)){
// cdbg("OKK");
// cdbg(i);
// cerr<<p[1]<<p[2]<<pp[1]<<pp[2]<<endl;
f[p[1]][p[2]][p[3]][p[4]][p[5]]
=min(f[p[1]][p[2]][p[3]][p[4]][p[5]],f[pp[1]][pp[2]][pp[3]][pp[4]][pp[5]]+v[i]);
}
}
// cdbg("ok");
int res=f[p[1]][p[2]][p[3]][p[4]][p[5]];
for(int i=1;i<=b;i++){
res+=(amt[i]-p[i])*orp[i];
}
ans=min(ans,res);
return ;
}
for(int i=0;i<=amt[x];i++){
p[x]=i;
dfs(x-1);
}
}
void solve(){
n=rd;
for(int i=1;i<=n;i++){
int l=rd;
for(int j=1;j<=l;j++){
int a=rd,b=rd;
e[i].pb(mp(a,b));
}
v[i]=rd;
}
b=rd;
for(int i=1;i<=b;i++){
id[rd]=i,amt[i]=rd,orp[i]=rd;
}
for(int i=1;i<=n;i++){
for(int j=0;j<e[i].size();j++){
e[i][j]=mp(id[e[i][j].pf],e[i][j].ps);
}
}
// cerr<<e[1][0].pf<<e[1][1].pf<<endl;
memset(f,0x3f3f,sizeof f);
f[0][0][0][0][0]=0;
dfs(b);
// cdbg(f[1][2][0][0][0]);
cout<<ans<<endl;
}
signed main(){
int T=1;
while(T--){
solve();
// if(T)puts("");
}
return 0;
}
超大背包¶
类型 #1 容量大，物品大（选的物品不多）¶
[SNOI2017] 英雄联盟
正在上大学的小皮球热爱英雄联盟这款游戏，而且打的很菜，被网友们戏称为「小学生」。
现在，小皮球终于受不了网友们的嘲讽，决定变强了，他变强的方法就是：买皮肤！
小皮球只会玩 \(\text{N}\) 个英雄，因此，他也只准备给这 \(\text{N}\) 个英雄买皮肤，并且决定，以后只玩有皮肤的英雄。
这 \(\text{N}\) 个英雄中，第 \(\text{i}\) 个英雄有 \(K_i\) 款皮肤，价格是每款 \(C_i\) Q 币（同一个英雄的皮肤价格相同）。
为了让自己看起来高大上一些，小皮球决定给同学们展示一下自己的皮肤，展示的思路是这样的：对于有皮肤的每一个英雄，随便选一个皮肤给同学看。
比如，小皮球共有 5 个英雄，这 5 个英雄分别有 \(\text{0,0,3,2,4}\) 款皮肤，那么，小皮球就有 \(3 \times 2 \times 4 = 24\) 种展示的策略。
现在，小皮球希望自己的展示策略能够至少达到 \(\text{M}\) 种，请问，小皮球至少要花多少钱呢？
输入格式
第一行，两个整数 \(\text{N,M}\)。
第二行，\(\text{N}\) 个整数，表示每个英雄的皮肤数量 \(K_i\)。
第三行，\(\text{N}\) 个整数，表示每个英雄皮肤的价格 \(C_i\)。
输出格式
一个整数，表示小皮球达到目标最少的花费。
共 10 组数据，第 \(\text{i}\) 组数据满足：\(\text{N} \le \max(5, \log_2^4i)\) 即 \(150\)
\(\text{100}\%\) 的数据：\(\text{M} \le 10^{17}, 1 \le K_i \le 10, 1 \le C_i \le 199\)。保证有解。
我们发现这里的总贡献是乘。我们想到 \(f_i\)表示得到i种策略的最小代价，但是i太大了。
因此我们考虑**交换值域和定义域**
\(f_i\)为花费i元得到的最大策略数
#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<<'\n';
#define rd read()
inline int read(){
int x;
cin>>x;
return x;
}
const int N=2e6+5;
const int M=2e5+5;
const int INF=1e18;
const int MOD=998244353;
/*
策略
我们发现这里的总贡献是乘。我们想到f_i表示得到i种策略的最小代价，但是i太大了。
因此我们考虑交换值域和定义域
f_i为花费i元得到的最大策略数
*/
int amt[N];
int f[N];
int c[N];
void solve(){
int n=rd,m=rd;
for(int i=1;i<=n;i++){
amt[i]=rd;
}
for(int i=1;i<=n;i++){
c[i]=rd;
}
// memset(f,1,sizeof f);
// cdbg(f[1]);
for(int j=1;j<=n;j++){
for(int i=N-1;i;i--){
for(int k=amt[j];k;k--){
if(i-c[j]*k>=0)f[i]=max(f[i],(f[i-c[j]*k]?f[i-c[j]*k]:1)*k);
// else break;
}
}
}
int fg=0;
for(int i=1;i<N;i++){
if(f[i]>=m){
cout<<i<<endl;
fg=1;
return ;
}
}
assert(fg);
}
signed main(){
int T=1;
while(T--){
solve();
// if(T)puts("");
}
return 0;
}
类型 #2 容量大 物品小 一个物品重复很多次¶
见同余最短路同余最短路
进程dp¶
例题 #1 [HNOI2001] 产品加工¶
题目描述
某加工厂有 A、B 两台机器，来加工的产品可以由其中任何一台机器完成，或者两台机器共同完成。由于受到机器性能和产品特性的限制，不同的机器加工同一产品所需的时间会不同，若同时由两台机器共同进行加工，所完成任务又会不同。
某一天，加工厂接到 \(n\) 个产品加工的任务，每个任务的工作量不尽一样。
你的任务就是：已知每个任务在 A 机器上加工所需的时间 \(t_1\)，B 机器上加工所需的时间 \(t_2\) 及由两台机器共同加工所需的时间 \(t_3\)，请你合理安排任务的调度顺序，使完成所有 \(n\) 个任务的总时间最少。
输入格式
第一行为一个整数 \(n\)。
接下来 \(n\) 行，每行三个非负整数 \(t_1,t_2,t_3\)，分别表示第 \(i\) 个任务在 A 机器上加工、B 机器上加工、两台机器共同加工所需要的时间。如果所给的时间 \(t_1\) 或 \(t_2\) 为 \(0\) 表示任务不能在该台机器上加工，如果 \(t_3\) 为 \(0\) 表示任务不能同时由两台机器加工。
输出格式
仅一行一个整数，表示完成所有 \(n\) 个任务的最少总时间。
对于所有数据，有 \(1\le n\le 6\times 10^3\)， \(0\le t_1,t_2,t_3\le 5\)。
这类背包的特点是：f_{i,j,k}表示A花费i时间，B花费j时间，处理了前k个物品，是否可行。
压维，就是f_{j,k}B花费j时间，处理了前k个物品，在A上花费的最小时间。
本题可以把A,B共同成立的提到最前面，这样就不会在中间留下空隙了。
/* Erica N */
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
#define itn 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;
}
#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...); }
const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
int a[N];
int b[N],c[N];
int f[2][N];
void solve(){
int n=rd;
for(int i=1;i<=n;i++){
a[i]=rd;
b[i]=rd;
c[i]=rd;
}
int s=0;
memset(f,0x3f3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++){
memset(f[i&1],0x3f3f,sizeof f[i&1]);
s+=max(a[i],max(b[i],c[i]));
for(int j=0;j<=s;j++){
if(b[i])f[i&1][j]=min(f[i&1][j],f[i&1^1][j]+b[i]);
if(a[i]&&j>=a[i])f[i&1][j]=min(f[i&1][j],f[i&1^1][j-a[i]]);
if(c[i]&&j>=c[i])f[i&1][j]=min(f[i&1][j],f[i&1^1][j-c[i]]+c[i]);
}
}
int ans=INF;
for(int i=0;i<=s;i++){
ans=min(ans,max(i,f[n&1][i]));
}
cout<<ans<<endl;
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}