多重背包¶
思想¶
类似完全背包，只不过k循环，枚举第i件物品取k份的条件改变了
注意¶
观察f[i][j]中保存的信息和题目，我们**不可以**把k循环去掉，请思考！
例题 #1¶
第一行二个数n(n≤500)，m(m≤6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。
接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可），其中v≤100，w≤1000，s≤10。 求此次购买能获得的最大的价值（注意！不是价格）。
解决
#include <bits/stdc++.h>
using namespace std;
int m, n, w[10005], c[10005], f[10005], s[10005];
int main() {
cin >> n >> m ;
for (int i = 1; i <= n; i++)
cin >> c[i] >> w[i] >> s[i];
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--)
for (int k = 0; k <= s[i]; k++) {
if (j - k * c[i] < 0)
break;
f[j] = max(f[j], f[j - k * c[i]] + k * w[i]);
}
}
cout << f[m];
return 0;
}
例题 #2 多重背包模板 Coins¶
题目描述
银国的人们使用硬币。他们有面值分别为 \(A_1, A_2, A_3, \dots, A_n\) 的硬币。有一天，托尼打开了他的储蓄罐，发现里面有一些硬币。他决定去附近的商店购买一块非常漂亮的手表。他想要支付准确的价格（不找零），而他知道手表的价格不会超过 \(m\) 。但他不知道手表的确切价格。
你需要编写一个程序，读取 \(n\)、\(m\)、\(A_1, A_2, A_3, \dots, A_n\) 以及对应的数量 \(C_1, C_2, C_3, \dots, C_n\) （表示托尼拥有的每种面值的硬币数量），然后计算托尼可以用这些硬币支付的价格数量（从 1 到 \(m\) 的所有价格）。
输入格式
输入包含多个测试用例（不超过 \(25\) 组）。每个测试用例的第一行包含两个整数 \(n (1 ≤ n ≤ 100)\) 和 \(m (m ≤ 100000)\)。第二行包含 \(2n\) 个整数，分别表示 \(A_1, A_2, A_3, \dots, A_n\) 和 \(C_1, C_2, C_3, \dots, C_n (1 ≤ A_i ≤ 100000, 1 ≤ C_i ≤ 1000)\)。最后一个测试用例以两个零结尾。
输出格式
对于每个测试用例，在单独的一行输出答案。
/*
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 ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
#define itn int
// #define inr intw
// #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 = 1e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
bitset<N> f;
itn ans;
int a[N];
void solve(){
itn n=rd,m=rd;
if(n+m==0)exit(0);
for(int i=0;i<n;i++){
a[i]=rd;
}
f.reset();
// cdbg("ok");
f[0]=1;
for(itn i=0;i<n;i++){
itn c=rd;
// 无优化：
// int s=0;
// while(c--&&s<N)f|=f<<a[i],s+=a[i];
for(itn j=0;c>(1<<j);j++){ //二进制优化
f|=f<<(a[i]<<j);
c-=1<<j;
}
f|=f<<(a[i]*c);
}
for(int i=1;i<=m;i++){
if(f[i])ans++;
}
// cdbg(ans);
cout<<ans<<endl;
ans=0;
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T=1;
while(T){
solve();
}
return 0;
}
例题 #3 [BalticOI 2022 Day1] Uplifting Excursion¶
题目描述
有 \(2m+1\) 种物品，重量分别为 \(-m,-m+1,\ldots, m-1,m\)。重量为 \(i\) 的物品有 \(a_i\) 个。
你需要拿走若干物品，使得这些物品重量之和恰好为 \(l\)。在此基础上，你需要拿尽可能多的物品。
问在物品重量之和恰好为 \(l\) 的基础上，你最多能拿多少物品。
思路¶
我们考虑这道题，应该就是一道背包的题目.但是同时我们发现，有一些物品的重量是可以抵消的，所以我们应该先选中这些物品。
好了，现在我们还有一些物品，以及一个需要被填满的，容量为l的且当前为空的背包。这里我们关注到一点，就是我们刚才的贪心枚举其实不一定正确——为了这里我们恰好填满容量为l的背包，我们可能不得不从用来抵消背包容量的物品（即重量为负的物品）中剔除一部分，以便于我们可以达到l的总重量。
我们发现，l实在是太大了，所以我们还可以继续地多拿一些物品。事实上，因为我们的l太大了，我们应该考虑如何减小这个值域。
为了避免分类讨论，我们可以在一开始就把所有物品取下，设所有物品的重量和为s，若s>l，那么我们每次选中最大的数删除，直到s≤l。这里我们注意到每个物品的价值都是1，所以这样的贪心是正确的。
若s
操作完后我们发现，现在背包还剩余的空间是<m的！现在我们看似就可以进行背包了。我们要考虑反悔操作。
我们给已经选择的物品赋负重量和负价值，没有选择的物品直接加入，然后跑多重背包即可。
代码¶
这里我们狠狠地指出，要弄明白偏移量和边界。（调了2小时）
/*
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
*/
#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');
}
const char el='\n';
const bool enable_dbg = 0;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s << ' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e5;
const int MOD = 1e9 + 7;
int used[N];
struct node{
int w,v;
}o[N];
int ans,f[2][N],cnt;
int n,m,l,a[N];
int sum;
void ins(int x){
int b=1;
int cur=a[x]-used[x],w=x-m;
dbg(x,cur);
while(cur){
if(b>cur)b=cur;//注意，只需要一次2^k，剩下的直接原数加入，不需要再二进制分解
o[++cnt]={w*b,b};
cur-=b;
b<<=1;
}
cur=used[x];
b=1;
while(cur){
if(b>cur)b=cur;
o[++cnt]={-w*b,-b};
cur-=b;
b<<=1;
}
}
void solve(){
m=rd,l=rd;
for(int i=0;i<=m*2;i++){
a[i]=rd;
if(i>m)continue;
sum+=a[i]*(i-m);
used[i]=a[i];
ans+=a[i];
}
for(int i=m+1;i<=2*m;i++){//优先加入小的
int num=min((l-sum)/(i-m),a[i]);
used[i]=num;
ans+=num;
sum+=num*(i-m);
}
for(int i=0;i<m;i++){//优先删小的,0不需要考虑
int num=min((l-sum)/(m-i),a[i]);
used[i]-=num;
ans-=num;
sum-=num*(i-m);
}
if(l-sum>m){
puts("impossible");
return ;
}
dbg("ok");
for(int i=0;i<=2*m;i++){
if(i==m)continue;
ins(i);
}
// dbg("ok");
//WA below
// memset(f,-0x3f,sizeof f);
// f[0][M]=0;
// for(int i=1;i<=cnt;i++){
// for(int j=M+m;j>=M-m;j--){
// f[i&1][j]=f[i&1^1][j];
// if(j>=o[i].w && j - o[i].w < N)
// f[i&1][j]=max(f[i&1][j],f[i&1^1][j-o[i].w]+o[i].v);
// }
// }
memset(f, -0x3f, sizeof f);
f[0][M] = 0;
for (int i=1;i<=cnt;i++){
for (int j=M+m*m;j>=0;j--)//注意边界（调了2hrs TT）
{
f[i&1][j]=f[(i-1)&1][j];
if(j>=o[i].w&&j-o[i].w<=M+m*m)f[i&1][j]=max(f[i&1][j],f[(i-1)&1][j-o[i].w]+o[i].v);
}
}
if(f[cnt&1][l-sum+M]+ans<0)puts("impossible");
else cout<<f[cnt&1][l-sum+M]+ans<<endl;
}
signed main() {
int T=1;
while(T--){
solve();
}
return 0;
}
对于所有数据，满足 \(1\leq m \leq 300\)，\(-10^{18}\le l \le 10^{18}\)，\(0\le a_i\le 10^{12}\)。
例题 #4 二进制分组优化 SUBSTRACT¶
题面翻译
现有一个数列 \(\{a_n\}\ (1 \le n,a_i \le 100)\)，你需要对它进行 \(n-1\) 次操作。其中第 \(i\) 次操作是：
-
选择一个正整数 \(t\ (1 \le t \le n-i)\)；
-
计算 \(d=a_t-a_{t+1}\)；
-
删除 \(a_t,a_{t+1}\) 两项；
-
在原来 \(a_t\) 的位置插入一项 \(d\)。
试构造一种操作方案，使得 \(n-1\) 次操作后数列中剩下的那个数恰好等于给定的数 \(T\ (|T| \le 10^4)\)（保证有解）。
输入格式： 第一行 \(n,T\)，后面 \(n\) 行 \(\{a_n\}\)。
输出格式： 依次输出 \(n-1\) 次操作中选择的 \(t\)，每个一行。
样例解释：
| 操作次数 | 数列 |
|---|---|
| \(0\) | \(\{12,10,4,3,5\}\) |
| \(1\) | \(\{12,6,3,5\}\) |
| \(2\) | \(\{12,6,-2\}\) |
| \(3\) | \(\{12,8\}\) |
| \(4\) | \(\{4\}\) |
二进制分组规则：
先将可以拆分成二进制的拆分为1+2+4+8+\dots
剩下的作为一整个物品即可。
/*
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 ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
#define itn int
// #define inr intw
// #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 = 1e9;
const int M = 1e5;
const int MOD = 1e9 + 7;
int v[N];
itn f[N];
int a[66];
void solve(){
int sum=0;
for(itn i=1;i<=6;i++)a[i]=rd,sum+=a[i]*i;
if(!sum)exit(0);
if(sum&1){
puts("Can't");
return ;
}
int cnt=0;
memset(f,0,sizeof f);
for(itn i=1;i<=6;i++){
for(int j=1;j<=a[i];j<<=1){
v[++cnt]=j*i;
a[i]-=j;
}
if(a[i])v[++cnt]=a[i]*i;
}
f[0]=1;
for(int i=1;i<=cnt;i++){
for(int j=sum/2;j>=v[i];j--){
f[j]|=f[j-v[i]];
}
}
if(f[sum/2])puts("Can");
else puts("Can't");
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T=1;
while(T){
solve();
}
return 0;
}
练习 #1 [USACO06DEC] The Fewest Coins G¶
农夫 John 想到镇上买些补给。为了高效地完成任务，他想使硬币的转手次数最少。即使他交付的硬 币数与找零得到的的硬币数最少。
John 想要买价值为 \(T\) 的东西。有 \(N\)（\(1 \le N \le 100\)）种货币参与流通，面值分别为 \(V_1,V_2,\dots,V_N\)（\(1 \le V_i \le 120\)）。John 有 \(C_i\) 个面值为 \(V_i\) 的硬币（\(0 \le C_i \le 10 ^ 4\)）。
我们假设店主有无限多的硬币， 并总按最优方案找零。**注意**无解输出 -1。
考虑我们有有限个价值为正的硬币，还有无线（inf）个价值为负的硬币。
每个硬币的重量为1，求最小重量。
/*
策略
*/
struct node{
int v,w;//价值 重量
}q[N];
int tot;
int f[N],c[N],v[N];
void solve(){
int n=rd,t=rd;
for(int i=1;i<=n;i++){
v[i]=rd;
}
for(int i=1;i<=n;i++){
c[i]=rd;
}
int tot=0;
for(int i=1;i<=n;i++){
v[i+n]=-v[i];
c[i+n]=INF;
}
for(int i=1;i<=n;i++){
itn k=1;
while(c[i]>=k){
q[++tot]={v[i]*k,k};
// cdbg(v[i]);
// cdbg(k);
// cdbg('\n');
c[i]-=k;
k<<=1;
}
if(c[i]){
q[++tot]={v[i]*c[i],c[i]};
}
}
int mid=tot;
for(int i=n+1;i<=2*n;i++){
itn k=1;
while(c[i]>=k){
q[++tot]={v[i]*k,k};
c[i]-=k;
k<<=1;
}
if(c[i]){
q[++tot]={v[i]*c[i],c[i]};
}
}
memset(f,0x3f3f,sizeof f);
f[0]=0;
for(int j=1;j<=mid;j++){
for(int i=1;i<=t*2;i++){
if(i-q[j].v>=0)f[i]=min(f[i],f[i-q[j].v]+q[j].w);
}
}
// cdbg(f[50]);
// cdbg("ok");
for(int j=mid+1;j<=tot;j++){
for(int i=t*2;i;i--){
if(i-q[j].v<=2*t)f[i]=min(f[i],f[i-q[j].v]+q[j].w);
}
}
if(f[t]>=INF)puts("-1");
else cout<<f[t]<<endl;
}
signed main(){
int T=1;
while(T--){
solve();
// if(T)puts("");
}
return 0;
}