Posted on 2010-08-05 12:44
MiYu 閱讀(566)
評論(0) 編輯 收藏 引用 所屬分類:
C/C++ 、
ACM ( DP ) 、
ACM ( 背包(DP) )
//MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
題目地址：
http://acm.hdu.edu.cn/showproblem.php?pid=1171
多重背包的題目, 可以直接轉換成 0-1背包來做, 因為是要分成盡量相等的2部分, 所以 背包大小 sum / 2 就可以了.
另外, 還有一點要注意 , 結束條件是 非負數, 而不是 -1 !! 我在這里 TLE了一下午............YM
代碼如下 :
//MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
#include <iostream>
using namespace std;
int V[51];
int M[51];
int bst[125005];
int main ()
{
int N;
while ( scanf ( "%d",&N ), N > 0 )
{
int sum = 0;
for ( int i = 1; i <= N; ++ i )
{
scanf ( "%d%d",&V[i], &M[i] );
sum += V[i] * M[i];
}
int total = sum;
sum /= 2;
memset ( bst, 0 , sizeof ( bst ) );
for ( int i = 1; i <= N; ++ i )
{
for ( int j = 1; j <= M[i]; ++ j )
{
for ( int k = sum; k >= V[i] ; k -= V[i] )
{
if ( bst[ k - V[i] ] + V[i] > bst[k] )
{
bst[k] = bst[ k - V[i] ] + V[i] ;
}
}
}
}
int other = total - bst[sum];
if ( other > bst[sum] )
{
swap ( other, bst[sum] );
}
printf ( "%d %d\n", bst[sum], other );
}
return 0;
}
下面的是奮斗哥的代碼 ,:
// Author: Tanky Woo
// HDOJ 1171
#include <iostream>
using namespace std;
int c1[250010], c2[250010];
int value[55];
int amount[55];
int main()
{
int nNum;
while(scanf("%d", &nNum) && nNum>0)
{
memset(value, 0, sizeof(value));
memset(amount, 0, sizeof(amount));
int sum = 0;
for(int i=1; i<=nNum; ++i)
{
scanf("%d %d", &value[i], &amount[i]);
sum += value[i]*amount[i];
}
memset(c1, 0, sum*sizeof(c1[0]));
memset(c2, 0, sum*sizeof(c2[0]));
for(int i=0; i<=value[1]*amount[1]; i+=value[1])
c1[i] = 1;
int len = value[1]*amount[1];
for(int i=2; i<=nNum; ++i)
{
for(int j=0; j<=len; ++j)
for(int k=0; k<=value[i]*amount[i]; k+=value[i])
{
c2[k+j] += c1[j];
}
len += value[i]*amount[i];
for(int j=0; j<=len; ++j)
{
c1[j] = c2[j];
c2[j] = 0;
}
}
for(int i= sum/2; i>=0; --i)
if(c1[i] != 0)
{
printf("%d %d\n", sum-i, i);
break;
}
}
return 0;
}