给出n中m件商品，每件上面有自己的价格，问能否分成价格和相等的两堆。
设这m件商品的价值总和为s，则应有 （s&1） == 0 且 s >>= 1可达。
若只是单纯的将此多重背包转化成01背包，则时间复杂度为 m* (s>>=1) ， 然后只看数据范围就知道要超时。
然后在《背包九讲》上看到了一个比较扯的关于只考虑可达性的完全背包的优化。
优化后的时间复杂度为 n*(s>>=1),但是我写完之后变成了 n*n*(s>>=1). . . . . .不过不要太当真。
总之这种方式只适合做 n 较小且只考虑可达性的完全背包。
设 f( i , j ) 表示只用前 i 种商品填充背包到达 j 时，第 i 种商品还剩多少件，-1表示此状态不可达。
递推代码如下：
for(i = 0;i < 6; ++i)
{
for(j = i+1;j <= sum; ++j)
{
if(i == 0)
{
if(ans[0][j-1] > 0)
{
ans[0][j] = ans[0][j-1]-1;
}
else
break;
}
else
{
for(int k = 0;k < i; ++k)
{
if(ans[k][j-i-1] >= 0)
{
ans[i][j] = a[i]-1;
}
if(ans[i][j-i-1] > 0)
{
ans[i][j] = max(ans[i][j],ans[i][j-i-1]-1);
}
}
}
}
}
AC代码 在HDU跑时400+，在POJ只用32 . . . .果然什么事都不能太当真
#include#include #include #include #include #include #include #include #define LL long long #define ULL unsigned long long #define PI (acos(-1.0)) #define EPS (1e-10) #pragma comment(linker,"/STACK:102400000,1024000") using namespace std; int ans[6][120010]; int main() { int i,j,k,a[6],sum,t,s; bool mark = true; int icase = 1; while(1) { for(sum = 0,i = 0,mark = false;i < 6; ++i) { scanf("%d",&a[i]); if(a[i]) { mark = true; sum += a[i]*(i+1); } } if(mark == false) return 0; printf("Collection #%d:\n",icase++); if((sum&1) == 0) { sum >>= 1; for(i = 0;i < 6; ++i) memset(ans[i],-1,sizeof(int)*(sum+3)); for(i = 0;i < 6; ++i) { a[i] = min(a[i],sum/(i+1)); ans[i][0] = a[i]; } for(i = 0;i < 6; ++i) { for(j = i+1;j <= sum; ++j) { if(i == 0) { if(ans[0][j-1] > 0) { ans[0][j] = ans[0][j-1]-1; } else break; } else { for(int k = 0;k < i; ++k) { if(ans[k][j-i-1] >= 0) { ans[i][j] = a[i]-1; } if(ans[i][j-i-1] > 0) { ans[i][j] = max(ans[i][j],ans[i][j-i-1]-1); } } } } } for(i = 0;i < 6; ++i) { if(ans[i][sum] != -1) { break; } } if(i < 6) printf("Can be divided.\n\n"); else printf("Can't be divided.\n\n"); } else { printf("Can't be divided.\n\n"); } } return 0; }