题目链接:Click
here~~
题意:
有价值为1~6的珠宝,每种价值的珠宝数量已经给出,问是否可以将价值平分。
解题思路:
又是一道平分问题,于是可以将问题转化为容量为 sum/2 的背包问题(sum为总价值)。
对于每种价值的物品 i ,是一个费用为 i ,价值为 i ,数量为num[i]的多重背包。
还用到了多重背包常用的二进制优化。
方法是:将第 i 种物品分成若干件物品替换以后的物品,其中,每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。
我们使这些系数分别为1,2,4,…,2^(k-1),num[i]-2^k+1,且k是满足num[i]-2^k+1>0的最大整数。
比如,num[i]为14,就将这种物品分为系数为1,2,4,7的四件物品。
如此,复杂度为O(n*∑log num[i]),优化了很多。
另外,当背包容量V很大(10^6),num[i]比较小(10^2)时,还可以用搜索做这类平分问题,下一篇会给出。
代码很好实现。下面是我写的,不算精简。
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define CLR(a,v) memset(a,v,sizeof(a))
int num[7],dp[60010];
int dig[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
int main()
{
int v,ncase = 0;
while(1)
{
int sum = 0;
for(int i=1;i<=6;i++)
{
scanf("%d",&num[i]);
sum += i*num[i];
}
if(sum == 0)
break;
printf("Collection #%d:\n",++ncase);
if(sum&1)
{
printf("Can't be divided.\n\n");
continue;
}
CLR(dp,0);
sum /= 2;
for(int i=1;i<=6;i++)
{
for(int d=0;num[i];d++)
{
if(num[i] >= dig[d])
{
v = i*dig[d];
num[i] -= dig[d];
}
else
{
v = i*num[i];
num[i] = 0;
}
for(int j=sum;j>=v;j--)
dp[j] = max(dp[j],dp[j-v]+v);
}
}
if(dp[sum] == sum)
printf("Can be divided.\n\n");
else
printf("Can't be divided.\n\n");
}
return 0;
}
从风神博客中抄了个模板,挺清楚的。
#include <stdio.h>
#include <string.h>
#define N 60006
#define max(a,b) a > b ? a : b
int V,num[7],dp[N];
void Bag_01(int c,int w)
{
for(int i=V;i>=c;i--)
dp[i] = max(dp[i],dp[i-c]+w);
}
void Bag_All(int c,int w)
{
for(int i=c;i<=V;i++)
dp[i] = max(dp[i],dp[i-c]+w);
}
void Bag_Multiple(int c,int w,int num)
{
if(c*num >= V)
{
Bag_All(c,w);
return ;
}
int k = 1;
while(k < num)
{
Bag_01(c*k,w*k);
num -= k;
k <<= 1;
}
Bag_01(c*num,w*num);
}
int main()
{
int v,ncase = 0;
while(1)
{
int sum = 0;
for(int i=1;i<=6;i++)
{
scanf("%d",&num[i]);
sum += i*num[i];
}
if(sum == 0)
break;
printf("Collection #%d:\n",++ncase);
if(sum&1)
{
printf("Can't be divided.\n\n");
continue;
}
memset(dp,0,sizeof(dp));
V = sum/2;
for(int i=1;i<=6;i++)
Bag_Multiple(i,i,num[i]);
if(dp[V] == V)
printf("Can be divided.\n\n");
else
printf("Can't be divided.\n\n");
}
return 0;
}
分享到:
相关推荐
HDU1059的代码
动态规划入门,hdu上的动态规划入门题的结题报告。 hdu 1171,hdu 1059,hdu 2159,hdu 2191,hdu 3496
背包问题的模板,可以解决各类背包问题,根据问题需要修改参数即可。试用于ACM初学者。
杭电ACM课件2014版之 (HDUACM201303版_07)背包专题
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类