- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
Acwing 278 数字组合 。
状态表示:二维 。
集合:所有从前 \(i\) 个数里面选,且和是 \(j\) 的选法的集合 。
属性:选法的数量 。
状态计算 分为 选 \(i\) 的所有方案 和 不选 \(i\) 的所有方案 。
不选 \(i\) 也就是从前 \(i-1\) 个数里面选,且和是 \(j\) 的方案数 \(f[i-1,j]\) 。
选 \(i\) 也就是从前 \(i-1\) 个数里面选,且和是 \(j-a_i\) 的方案数,注意是 += ,因为我们算的是数量而不是最大值 。
注意当 \(j=0\) 也是有一种方案的,要初始化为 \(1\) 。
#include <iostream>
using namespace std;
const int N = 105, M = 10005;
int f[N][M], a[N];
int n,m;
int main()
{
cin>>n>>m;
f[0][0]=1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
f[i][0]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j]+=f[i-1][j];
if(j>=a[i]) f[i][j]+=f[i-1][j-a[i]];
}
}
cout<<f[n][m];
return 0;
}
优化也很简单,参考01背包的优化方式 。
这里不过多赘述,上代码 。
#include <iostream>
using namespace std;
const int N = 10005;
int f[N];
int main()
{
int n,m;
cin>>n>>m;
f[0]=1;
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
for(int j=m;j>=a;j--)
f[j]+=f[j-a];
}
cout<<f[m];
return 0;
}
这个标题有些迷惑,什么是平分子集,有什么实际运用吗?
平分子集大体意思是给你几个数,把这些数分成两组,问你最小的差值是多少?
我们可以将数的总和记录下来,然后将这个数除以2,再从数组里面挑数字尽可能装满这个背包 。
解释一下:想要两个子集差值最小,那么这个值最小为0,也就是相等,那么我们就尽可能选出一些数字接近这个一半,越接近差值就越小 。
首先来一道比较裸的题 巧分配 。
只需要按照上文说的方法再套上01背包的模板就行了,不过多解释 。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 50005;
int a[N];
int main()
{
int n,t;
cin>>t;
while(t--)
{
int f[N]={0};
cin>>n;
int sum=0;
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
for(int i=1;i<=n;i++)
for(int j=sum/2;j>=a[i];j--)
f[j]=max(f[j],f[j-a[i]]+a[i]);
cout<<sum-f[sum/2]-f[sum/2]<<endl;
}
return 0;
}
来一个进阶版本 kkksc03考前临时抱佛脚 。
题目中说的有4门学科容易误导,让人认为是分组背包什么的,实际上只相当于多组测试数据罢了,那么我们就把目光聚焦到一组上面 。
我们可以发现可以同时解决两个问题,那么想要这个特性运用的最划算,那么肯定是需要左脑和右脑处理的时间的差值最小,那么这个问题就转换成了平分子集问题,不过需要注意的是,这里求的是总时间,因为左脑和右脑只能处理同一科,所以如果左脑处理完了,左脑还得等右脑,所以需要取一个最大值,最后将每次取得的结果累加就行了 。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1005;
int s[5];
int f[N],a[N];
int main()
{
int res=0;
for(int i=1;i<=4;i++) cin>>s[i];
for(int t=1;t<=4;t++)
{
memset(f,0,sizeof f);
int sum=0;
for(int i=1;i<=s[t];i++) cin>>a[i],sum+=a[i];
for(int i=1;i<=s[t];i++)
for(int j=sum/2;j>=a[i];j--)
f[j]=max(f[j],f[j-a[i]]+a[i]);
res+=max(sum-f[sum/2],f[sum/2]);
}
cout<<res;
return 0;
}
[USACO03FALL]Cow Exhibition G 奶牛博览会 。
题目要求两个指数不能是负数,且和最大,不能看作简单的01背包来处理 。
我们可以设计一下状态,假设 \(TS\) 为正数(弄一个偏移量,把负数变成正数)。状态 \(f[i]\) 表示花费 \(i\) 的聪明指数能得到的最大的风趣指数 。
这里有几个问题需要注意一下 。
正数和负数为什么会不一样?
在正数中, \(j > j-v[i]\) ,我们想要求得 \(f[j]\) 的话就必须要使用 \(i-1\) 层的 \(f[j-TS[i]]\) 所以如果从小到大的话会导致 \(f[j-TS[i]]\) 先算,这样用的就是 \(i\) 层的 \(f[j-TS[i]]\) 了,与原本二维的状态是不符的 。
而在负数中, \(j<j-TS[i]\) ,我们想要球的 \(f[j]\) 还是要用 \(i-1\) 层的 \(f[j-TS[i]]\) ,如果我们从大到小的话就会导致 \(f[j-TS[i]]\) 先算,与之前是同一个道理,所以需要区别对待 。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 105, M = 200005;
int f[M],TS[N],TF[N]; //当 TS 的值达到 i 的时候,TF 的最大值
int main()
{
int n,m=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>TS[i]>>TF[i];
if(TS[i]>0) m+=TS[i];
}
memset(f,-0x3f,sizeof f);
f[m]=0;
for(int i=1;i<=n;i++)
{
//正数的情况
if(TS[i]>0)
for(int j=m*2;j>=TS[i];j--)
f[j]=max(f[j],f[j-TS[i]]+TF[i]);
//负数的情况
else
for(int j=0;j<=m*2+TS[i];j++)
f[j]=max(f[j],f[j-TS[i]]+TF[i]);
}
int ans=0;
for(int i=0;i<=m;i++)
{
if(f[i+m]>0) ans=max(ans,f[i+m]+i);
}
cout<<ans;
return 0;
}
由于完全背包的最终版本和01背包非常像,这里就不多赘述,具体看上文提到的01背包完全装满求方案数 。
#include <iostream>
using namespace std;
const int N = 10005;
int f[N];
int main()
{
int n,m;
cin>>n>>m;
f[0]=1;
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
for(int j=a;j<=m;j++)
f[j]+=f[j-a];
}
cout<<f[m];
return 0;
}
进阶版本 NOIP2018 提高组 货币系统 。
由于纸币有无穷张,所以是完全背包 。
首先来解释一下题目是什么意思,题目要求我们设计一个等价的货币系统,相当于给出的货币系统有的面值是没有用的,我们将这个货币系统优化一下,去掉几种面值,但是不能多表示一些面值,也不能少表示一些面值 。
那我们可以将现有的货币系统能表示的所有面值都搞出来,然后看需要什么面值的钱才能表示这个面值 。
换句话讲,例如说如果 5 这个面值 只有一种表示方法,那么一定是1张5元的钱,那么这张钱就不能省去,是必要的 。
如果有两种表示方法的话,那么就可以被替代了,由于面值只能相加不能相减,所以这两种方法其中一定有一种是由比这张钱价值小的钱凑出来的,所以我们就不需要新的钱了 。
另外有可能对无穷张这个点有些疑惑,无穷张不管是 2张 还是 3张 表示的面值也一定用给出的货币系统的面值凑出来,所以无需考虑 。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 25005;
int f[N],a[105];
int main()
{
int T; cin>>T;
while(T--)
{
memset(a,0,sizeof a); memset(f,0,sizeof f);
int maxx=0,ans=0;
int n; cin>>n;
f[0]=1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
maxx=max(maxx,a[i]);
}
for(int i=1;i<=n;i++)
for(int j=a[i];j<=maxx;j++)
f[j]+=f[j-a[i]];
for(int i=1;i<=n;i++)
if(f[a[i]]==1) ans++;
cout<<ans<<endl;
}
return 0;
}
摆花 。
与之前的一样,不过要注意的是,分组里面枚举的 \(k\) 是下标,而这里的体积都为1,所以说如果从 \(0\) 开始枚举的话要 \(-(k+1)\) 。
#include <iostream>
using namespace std;
const int N = 1005;
int f[N];
int main()
{
int n,m;
cin>>n>>m;
f[0]=1;
for(int i=1;i<=n;i++)
{
int a; cin>>a;
for(int j=m;j>=0;j--)
{
for(int k=0;k<a;k++)
{
if(k<=j) f[j]=(f[j]+f[j-k-1])%1000007;
}
}
}
cout<<f[m]%1000007;
return 0;
}
最后此篇关于背包问题变式总结的文章就讲到这里了,如果你想了解更多关于背包问题变式总结的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
COW 不是奶牛,是 Copy-On-Write 的缩写,这是一种是复制但也不完全是复制的技术。 一般来说复制就是创建出完全相同的两份,两份是独立的: 但是,有的时候复制这件事没多大必要
我是一名优秀的程序员,十分优秀!