惠东网站设计,引航科技提供网站建设,做搜狗pc网站优化首,网站做关键词排名有必要吗Hdu链接 文章目录题目描述题意#xff1a;题解#xff1a;代码#xff1a;题目描述 输入描述: 输出描述: 示例1 输入
1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0输出
Collection #1:
Cant be divided.Collection #2:
Can be divided.题意#xff1a;
有价值分别是1~6的6种…Hdu链接
文章目录题目描述题意题解代码题目描述 输入描述: 输出描述: 示例1 输入
1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0输出
Collection #1:
Cant be divided.Collection #2:
Can be divided.题意
有价值分别是1~6的6种大理石每种大理石的数量是ni问能否将这些大理石分成完全相同的两部分
题解
这个题和hdu 2844 Coins做法基本一样不过本题要稍微转变下思路 我们考虑用背包方法来做题目给了数量价值却没有给总容量和体积。我们结合题意思考一下要分成价值完全相同的两份其实就是找到一份大理石使得这一份的价值是总价值的一半。如果我们这样想我们就会发现总容量其实就是大理石总价值的一半每个大理石的体积就是其价值我们要做的就是找到“一些商品使得其体积满足总容量一半的情况是否存在”这不就可以用混合背包来做。 对于数量多的用完全背包对于数量少的用多重背包
代码
#includebits/stdc.h
using namespace std;
int a[8];
int sum0;
int dp[120005];
bool f0;;
void zerone(int cost,int val)
{for(int isum;icost;i--){dp[i]max(dp[i],dp[i-cost]val);}}
void complet(int cost)
{for(int icost;isum;i)dp[i]max(dp[i],dp[i-cost]cost);
}
void mul(int cost,int val,int num)
{if(cost*numsum){complet(cost);return ;}for(int i1;inum;i1){zerone(i*cost,i*val);num-i;}zerone(num*cost,num*val);
}
int main()
{int case10;while(cina[1]a[2]a[3]a[4]a[5]a[6]){case1;f0;memset(dp,0,sizeof(dp));if(a[1]0a[2]0a[3]0a[4]0a[5]0a[6]0)break;printf(Collection #%d:\n,case1);suma[1]*12*a[2]3*a[3]4*a[4]5*a[5]6*a[6];if(sum%2){printf(Cant be divided.\n);printf(\n);continue;}sum/2;for(int i1;i6;i){mul(i,i,a[i]);//花费价值数量 }if(dp[sum]sum)f1;if(f1)coutCan be divided.endl;else coutCant be divided.endl;coutendl;}return 0;
}
