计算total value如果为奇数则不可分；
否则平分total value 记做V，转化为多重背包cost和weight相等都为i(1..6),数量为输入的数据记为n[i];背包的容量为V。然后利用多重背包的优化算法（转化为0,1和完全背包）计算是否能装满容量为V的背包。在这里装满的条件是在初始化的时候对f(记录最优值的数组)有f[0]=0,其他都等于一个大的负数。最后如果F[v]=V则可以分解。以下是代码：
#include <iostream>

using namespace std;
const int MAX=120000;
const int len=7;
int f[MAX];
int n[len];
int V;
const int init=-9999;
int max(int a,int b)
{
    return a>b?a:b;
}
void zeroOnePack(int cw)
{
    for(int v=V;v>=cw;v--)
    f[v]=max(f[v],f[v-cw]+cw);
}
void completePack(int cw)
{
    for(int v=cw;v<=V;v++)
    f[v]=max(f[v],f[v-cw]+cw);
}
void multiplePack(int cw,int amount)
{
    if(cw*amount>V)
    {
        completePack(cw);
        return;
    }
    int k=1;
    while(k<amount)
    {
        zeroOnePack(k*cw);
        amount=amount-k;
        k=k*2;
    }
    zeroOnePack(amount*cw);
}
int main()
{
    int count=0;
    while(1)
    {
        count++;
        int i;
        int bin=0;
        int sum=0;
        for(i=1;i<len;i++)
        {cin>>n[i]; bin|=n[i];sum+=i*n[i];}
        if(bin==0) break;
        if(sum%2!=0)
        cout<<"Collection #"<<count<<":\n"<<"Can't be divided."<<endl<<endl;
        else
        {
            sum/=2;
            V=sum;
            f[0]=0;
            for(i=1;i<=V;i++)
                f[i]=init;//f的初始化要考虑是否装满背包
            for(i=1;i<len;i++)
            multiplePack(i,n[i]);
            if(f[V]!=V)
             cout<<"Collection #"<<count<<":\n"<<"Can't be divided."<<endl<<endl;
            else
             cout<<"Collection #"<<count<<":\n"<<"Can be divided."<<endl<<endl;
        }

    }
    return 0;
}

• Re:01背包部分由缺陷 (138) 422803902 2013-01-30 22:08:18
  • Re:01背包部分由缺陷 (144) 422803902 2013-01-30 22:10:08
    • Re:01背包部分由缺陷 (18) witstorm 2017-11-24 20:21:44
      • Re:01背包部分由缺陷 (44) witstorm 2017-11-24 20:27:20
        • Re:01背包部分由缺陷 (842) pipipapasha 2023-10-14 23:47:54