【POJ1014】Dividing (动态规划,多重背包)

Categories: 数据结构和算法
Tags: ,
Comments: 4 Comments
Published on: 2011 年 04 月 25 日

思想:本题是找按价值均分大理石的方案是否存在,由于分配时不能破坏大理石,所以有个显而易见的剪枝:当所有的大理石的总价值为奇数时肯定不能被均分。把问题转化一下即:由一个人能否从原大理石堆中取出总价值为原来一半的大理石,本题的主要算法是动态规划,数组flag代表状态,设总价值为sum.当flag[k]==true时,说明,可以有一人获得价值k,另外一人获得价值V-k的大理石分配方案。反之若flag[k]=false说明这种分配方案不存在.我们的任务就是计算出flag[sum/2]是true还是false,显然有flag[0]==true的方案存在,即一个人什么都不分,另外一个人拿走全部的大理石.
设i(1<<6)为石头的价值,试想若flag[k]==true,如果能再向k中增加一价值为i的大理石,则flag[k+i]==true必然成立.石头有两个属性,一个是价值另一个是数量,这里array[i]代表价值为i的大理石的数量,我们根据其中一个属性:价值来划分阶段。即for (int i=1;i<=6;i++),flag[k]表示状态是否存在(这里的状态是指能否从原石头堆中分出价值为k的新石头堆)。在初始阶段是i=1,初始状态是flag[0]=true,max代表目前满足flag[k]==true这一条件的k的最大值。
for(int j=max;j>=0;j--)
//从当前最大值flag开始,根据前面提到的flag[j]==true成立则flag[j+i]==true亦成立的理论,在原有状态flag[j]==true已存在的条件下加入stone[i]阶段的石头,得到新的状态

还是举个例子吧:3 0 1 2 0 0

flag[] : sum/2=6

i 0 1 2 3 4 5 6
flag[] : 1 0 0 0 0 0 0

对于i=1 array[1] = 3 因为flag[0] = true,所以flag[1], flag[2], flag[3]都变为true:

i 0 1 2 3 4 5 6
flag[] : 1 1 1 1 0 0 0

对于i=2 array[2] = 0 不考察

对于i=3 array[3] = 1 因为flag[0] flag[1], flag[2], flag[3]= true,所以flag[3], flag[4], flag[5],flag[6]都变为true:

i 0 1 2 3 4 5 6
flag[] : 1 1 1 1 1 1 1

等等等等,我们的任务是判断flag[sum/2]是否为真。

这样程序的基本框架就有了,

这样问题就解决了,submit,结果超时,从joj上试了一下,结果ac,6s多,距离poj的1s还很远。我们考察如果flag[j+k*i]已经等于true,就不用继续循环下一个k了,直接break就可以了,具体原因是这样的:

假设现在flag[]的序列是这样的:1 1 0 1 1 0 1 1 0 1,当前考察的是 i=3;array[i]=5,就是要在这个基础上加上5个3,按照程序的意思,从最后一个1开始依此加上3,将其值变为1,一共加上5个,然后在倒数第二个1上依此加上3,将其值变为1,一共加上5个,这个过程不会遇见flag=1的情况,给倒数第三个1依此加3的时候,会遇到:flag=1,这个时候就可以break了,因为这时候还需要加的4个3都在最后一个1加5个3时候加过了,这里要注意的是,给每个1加上3时候,只会遇到”旧的”flag=1,不会遇到新增加的flag=1,而旧的1已经加过了array[i]个i,所以就不用加了,直接退出就行了。

修改后的代码:

 

#include <iostream>  
#include <cstring>  
using namespace std;  
bool flag[60005];  
int main(){  
    int arr[7],n=1,sum,lastone;  
    while(n){  
        memset(flag,0,sizeof(flag));  
        flag[0]=1;  
        sum=lastone=0;  
        for (int i=1;i<=6;i++)  
        {cin>>arr[i]; sum+=arr[i]*i;}  
        if(sum==0) break;  
        cout<<"Collection #"<<n<<":\n";  
        if(sum&1){  
            cout<<"Can't be divided.\n\n";  
            n++;  
            continue;  
        }  
        sum=sum>>1;  
        for (int i=1;i<=6;i++){  
            if(arr[i]>0 && flag[sum]!=true){  
                for (int j=lastone;j>=0;j--){  
                    if(flag[j] && flag[sum]!=true){  
                        for (int k=1;k<=arr[i];k++){  
                            if(j+k*i==sum)  
                            {flag[j+k*i]=true;break;}  
                            if(j+k*i>sum||flag[j+k*i])  
                                break;  
                            flag[j+k*i] = true;  
                        }  
                    }  
                }  
            }  
            lastone += arr[i]*i;  
            if(lastone>sum) lastone = sum;  
        }  
        if(flag[sum])  
            cout<<"Can be divided.\n\n";  
        else   
            cout<<"Can't be divided.\n\n";  
        n++;  
    }  
}  

我猜你可能也喜欢:

4 Comments - Leave a comment
  1. hzs说道:

    谢谢了。理解了,没有仔细看,原来这里还有判断,if(flag[j] && flag[sum]!=true),学习了~~小生还有很多OJ题不太理解,有时间还望大牛指导~~~再次感谢

  2. hzs说道:

    大牛,偶初学者,可以解释一下if(lastone>sum) lastone = sum;这是为什么么,这样的话,不是说flag[sum]=true了吗

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日