首页 > 代码库 > 编程练习赛11B 物品价值(装压dp)
编程练习赛11B 物品价值(装压dp)
题意:每个物品有m(m<=10)种属性和一个价格,你有n种物品从中任意选择一些物品,让每种属性恰好有奇数个物品拥有,输出满足条件的最大价值和
题解:一看就是明显的01背包问题,但是价格乘以个数的平方太大了,所有无法直接枚举价格进行背包
首先可以发现只分成奇数与偶数、而且m很小,所以可以对于每个物品的属性使用二进制压缩,此位有这个属性就变成1,否则为0
然后因为同奇同偶相加为偶、否则为奇,类似异或的规则,所以两个物品和在一起就是用两个压缩数进行异或
最后可以发现虽然不能枚举价格,但是压缩后的数只能是0到1023、这1024种可能,所以可以先枚举个数n,再枚举压缩后的数
注意代码中写的几个点
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<iomanip> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<30; const ll INF=1LL<<60; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=1050; int dp[Max][Max]; int num[Max],value[Max]; int Solve(int n,int m) { for(int i=0; i<n; ++i) { for(int j=1; j<(1<<m); ++j) { if(j) dp[i][j]=-Inf; else//必须是从0开始 dp[i][j]=0; } } int res=0; for(int i=1; i<=n; ++i) { for(int j=0; j<(1<<m); ++j) { dp[i][j]=max(dp[i-1][j],dp[i-1][j^num[i]]+value[i]);//注意动归方程式 } res=max(res,dp[i][(1<<m)-1]); } return res; } int main() { int t; int n,m; scanf("%d",&t); while(t--) { scanf("%d %d",&n,&m); int temp,temp2; for(int i=1; i<=n; ++i) { scanf("%d %d",&value[i],&temp); num[i]=0; for(int j=0; j<temp; ++j) { scanf("%d",&temp2); num[i]=(num[i]|(1<<(temp2-1)));//使用的是按位或 } } printf("%d\n",Solve(n,m)); } return 0; }
编程练习赛11B 物品价值(装压dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。