首页 > 代码库 > HDU 1171 Big Event in HDU（0-1背包）
HDU 1171 Big Event in HDU（0-1背包）
http://acm.hdu.edu.cn/showproblem.php?pid=1171
题意：给出一系列的价值，需要平分，并且尽量接近。
思路：0—1背包问题。
0-1背包问题也就是有n种物品且每种只有一个。第i个物品的体积为vi，重量为wi。选择一些物品装到背包中，使得体积不超过背包的前提下重量尽可能大。
用f（i，j）表示“把前i个物品装到容量为j的背包中的最大总重量，其状态转移方程就是：
f(i,j)=max{ f(i-1,j）,f(i-1,j-v[i])+w[i] }
所以在第i个物品的时候，我们需要判断是装还是不装，f(i-1,j)是不装,f(i-1,j-v[i])+w[i] 代表把第i件装入背包后得总价值，比较两者的大小，选择价值大的存入现在的背包。
f(i-1,j-v[i])是指当把前i件物品装入一个容量为j-v[i]大小的背包中的最大总重量。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 int v[5010]; 7 int dp[300000]; 8 9 int main()10 {11 //freopen("D:\\txt.txt", "r", stdin);12 int n,a,b;13 while (cin >> n && n > 0)14 {15 memset(v, 0, sizeof(v));16 memset(dp, 0, sizeof(dp));17 int k = 0;18 int sum = 0;19 for (int i = 0; i < n; i++)20 {21 cin >> a >> b;22 while (b--)23 {24 v[k++] = a;25 sum += a;26 }27 }28 for (int i = 0; i < k; i++)29 {30 for (int j = sum / 2; j >= v[i]; j--)31 dp[j] = max(dp[j], dp[j - v[i]] + v[i]);32 }33 cout << sum - dp[sum / 2] << " " << dp[sum / 2] << endl;34 }35 return 0;36 }
HDU 1171 Big Event in HDU（0-1背包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。