2 10 1 20 1 3 10 1 20 2 30 1 -1
20 10 40 40
代码：
/**
* 本题题意：
* 给出每种石头的重量和个数，求尽量将这些石头分成两堆时，两堆石块的重量
* 这里消耗和价值都是石块的重量
* 解题思路：V=sum/2
*/
#include <string.h>
#include <stdio.h>
#define maxn 500005
int max(int a, int b){
if (a > b)return a;
return b;
}
int dp[maxn];
int weight[maxn];
int number[maxn];
int V;
//01
void zeroonepack(int c)
{
for (int v = V; v >= c; v--)
dp[v] = max(dp[v], dp[v - c] + c);
}
//完全
void completepack(int c)
{
for (int v = c; v <= V; v++)
dp[v] = max(dp[v], dp[v - c] + c);
}
//多重
void mupack(int c, int p)
{
if (c*p >= V)
completepack(c);
else
{
int k = 1;
while (k < p)
{
zeroonepack(k*c);
p = p - k;
k = k * 2;
}
zeroonepack(p*c);
}
}
int main()
{
int n;
while (scanf("%d", &n), n >= 0)
{
int sum = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &weight[i], &number[i]);
sum += weight[i] * number[i];
}
V = sum / 2;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++)
mupack(weight[i], number[i]);
int x = dp[V];
int y = sum - x;
if (x > y)
printf("%d %d\n", x, y);
else
printf("%d %d\n", y, x);
}
return 0;
}
hdu 1171 Big Event in HDU 多重背包,布布扣,bubuko.com
hdu 1171 Big Event in HDU 多重背包
原文：http://blog.csdn.net/u012964281/article/details/26400161