Dividing (多重背包 搜索)
Dividing (多重背包 搜索)
1944864971 发表于2年前
Dividing (多重背包 搜索)
  • 发表于 2年前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

移动开发云端新模式探索实践 >>>   

/
第一个多重背包题目 真的不理解二进制优化
/http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?cid=10594&pid=1001&ojid

以下是用二进制优化的 不会超时

include<stdio.h>

include<string.h>

include

include

using namespace std;
int dp[200000],a[7];
void zeroOne(int weiht,int value,int c)
{
for(int j=c;j>=weiht;j--)
dp[j]=max(dp[j],dp[j-weiht]+value);
}
void complelet(int weight,int value,int c)
{
for(int j=weight;j<=c;j++)
dp[j]=max(dp[j],dp[j-weight]+value);
}
void duoChong(int weight,int value,int count,int c)
{
if(count*value>=c)complelet(weight ,value,c);
else
{
int k=1;
while(k

include<string.h>

include

include

using namespace std;
int dp[200000],a[7],w[7];
int main()
{
int count=0;
while(1)
{
int sum=0;
for(int i=1; i<=6; i++)
{
scanf("%d",&a[i]);
sum+=a[i]*i;
w[i]=i;
}
if(sum==0)break;
printf("Collection #%d:\n",++count);
if(sum%2==1)
{
printf("Can't be divided.\n\n");
continue;
}
int c=sum/2;
memset(dp,0,sizeof(dp));
for(int i=1; i<=6; i++)
for(int k=1; k<=a[i]; k++)//有限个数量(超时)
for(int j=c; j>=w[i]; j--)
dp[j]=max(dp[j],dp[j-w[i]]+w[i]);
printf("sum/2=%d\n",dp[sum/2]);
if(dp[c]==sum/2)printf("Can be divided.\n\n");
else printf("Can't be divided.\n\n");
}
return 0;
}

下面是搜索做的 比多重背包快了很多

include<stdio.h>

include<string.h>

include

include

using namespace std;
int op=0;
int mid;
int a[8];
void dfs(int cnt,int sum)
{
if(op)return;
if(sum==mid)
{
op=1;
return ;
}
for(int i=cnt; i>=1; i--)
{
if(a[i])
if(sum+i<=mid)
{
a[i]--;
dfs(i,sum+i);
}
}
}
int main()
{
int count=0;
while(1)
{
int sum=0;
for(int i=1; i<=6; i++)
{
scanf("%d",&a[i]);
sum+=i*a[i];
}
if(sum==0)break;
printf("Collection #%d:\n",++count);
if(sum%2==1)
{
printf("Can't be divided.\n\n");
continue;
}
mid=sum/2;
op=0;
dfs(6,0);
if(op)printf("Can be divided.\n\n");
else printf("Can't be divided.\n\n");

}
return 0;

}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: