HDU1171 Big Event in HDU(01背包的转化，多重背包)

本文主要是介绍HDU1171 Big Event in HDU(01背包的转化，多重背包)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

Big Event in HDU

  
2
10 1
20 1
3
10 1 
20 2
30 1
-1

  
20 10
40 40

因为题目要求要尽量平均分配，所以我们可以先将总价值sum求出，然后得出其分配的平均值为sum/2,要注意这个答案可能为小数，但是又因为sum是整数，所以最后得出的sum/2是要小于等于实际的值。将这个结果进行01,背包，可以得出其中一个学院所得的最大价值，而另一个学院的最大价值也可以相应的得到，而前者必定小于等于后者。和邮票分你一半，zb的生日也比较相似

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int a[5005];
int dp[250005];
int main()
{int n;while(1){
//sum的一半一定是scanf("%d",&n);if(n<0)return 0;//为负数的时候结束输入mem(a,0);mem(dp,0);//初始化int sum=0,l=0;int value,num;//价值和数量for(int i=0; i<n; i++){scanf("%d %d",&value,&num);for(int j=0;j<num;j++){a[l++]=value;//把价值存入数组，转化成01背包问题sum+=value;//将sum求和}}for(int i=0; i<l; i++)//以一半的sum进行01背包for(int j=sum/2; j>=a[i]; j--)dp[j]=max(dp[j],dp[j-a[i]]+a[i]);printf("%d %d\n",sum-dp[sum/2],dp[sum/2]);}return 0;
}

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int value[5005];
int num[5005];
int dp[250005];
int main()
{int n;while(1){//sum的一半一定是scanf("%d",&n);if(n<0)return 0;//为负数的时候结束输入mem(value,0);mem(num,0);mem(dp,0);//初始化int sum=0;for(int i=0; i<n; i++){scanf("%d %d",&value[i],&num[i]);sum+=value[i]*num[i];//算出总价值}for(int i=0; i<n; i++)//进行多重背包for(int j=1; j<=num[i]; j++)for(int k=sum/2; k>=value[i]; k--)dp[k]=max(dp[k],dp[k-value[i]]+value[i]);printf("%d %d\n",sum-dp[sum/2],dp[sum/2]);}return 0;
}

这篇关于HDU1171 Big Event in HDU(01背包的转化，多重背包)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！