题解 P1537 【弹珠】

zyzzyzzyzzyz

2018-08-19 09:37:30

Solution

# 朴素的多重背包 #### 本蒟蒻的第一篇题解 ~~勿喷~~ 虽然有大佬已经提到过该做法,但没有代码,本蒟蒻在此补充 PS:大佬请略过本题解,建议dp初学者看 ## 正文: 首先要了解多重背包的含义: “给定N种物品,其中第i种物品的体积为Vi,价值为Wi, 并且有Ci个。有一个容量为M的背包,要求选择若干个物 品放入背包,使得物品总体积不超过M的前提下,物品总 价值最大。” ——《算法竞赛》 李煜东 对应本题,给出了6种价值的石头,每种石头“体积”与“价值” 都为i(1<=i<=6),可以选a[i]个;而题目中的要求是是否 存在 某种分配方式,使得背包的总价值为s/2(s为所有石头的价值 总和)。 因此对递推式进行一点小改动, 将f[i][j]=min(f[i-1][j-i*k],f[i][j])中的min改成sum即可(代码中会提到这一段)。 (另外,f[i][j]的含义:在选择1~i种物品、总价值为j的情况下的方案数) 因此,我们的思路就很清晰了: 1.确定状态转移方程:f[i][j]=min(f[i-1][j-i*k]; 2.确定边界:f[i][i*j]=1(j<=a[i]); 3.求解:f[i][s/2]是否非0(1<=i<=6) 上代码: ```cpp #include<bits/stdc++.h> using namespace std; int a[7],s=0,x,j,mark; long long f[7][60010];//这里的f用longlong存储,可以统计每种价值的表示方式数。当然本题不需要,用bool来存储是 //否可表就可以了 inline int rd(){//读优 int ans=0,flag=1; char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')flag=-1,ch=getchar(); while(ch>='0'&&ch<='9'){ ans=ans*10+ch-48; return ans*flag; } int main(){ for(register int i=1;i<=6;i++){//读入第一组数据 a[i]=rd(); s+=a[i]*i; } int i1=0; while(s!=0){//当s等于0时,输入结束 i1++;//i1记录第几组数据 mark=0,memset(f,0,sizeof(f));//初始化 cout<<"Collection #"<<i1<<':'<<endl; if(s&1==1)cout<<"Can't be divided."<<endl<<endl;//若s为奇数,一定不可分 else{ s=s/2; for(register int i=1;i<=6;i++){ for(register int j=1;j<=a[i];j++){ f[i][i*j]=1;//边界;若价值为i*j,则一定能被i表示(j<=a[i]) } } for(register int i=1;i<=6;i++){ for(register int j=i;j<=s;j++){ for(register int k=0;k<=a[i];k++) if(j>i*k) f[i][j]+=f[i-1][j-i*k];//转移方程 } } for(register int i=1;i<=6;i++){ if(f[i][s]){//存在一种表示s的方式 mark=1; printf("Can be divided.\n\n"); break; } } if(mark==0){ printf("Can't be divided.\n\n"); } } s=0; for(register int i=1;i<=6;i++){ a[i]=rd(); s+=a[i]*i; }//读入下一组数据 } return 0; } ```