The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 1276-Cash Machine 特殊情况下的背包问题+强剪枝

今天又做了一个背包的题目,有点郁闷~如果单纯只考算法的话应该是很容易的,可是由于数据范围太大,一直都过不了。。。汗~
TLE了2个小时,自己尝试了N种剪枝方法但还是过不去。最后无奈只好到网络上搜索了一下,借用了网上大牛代码中的一个剪枝方法,才过掉这道题的。。。
刚开始的时候我是这么写的,没有任何剪枝,结果当然是TLE啦:

#include <iostream>
#include
<cstdio>
#include
<cmath>
#include
<algorithm>
using namespace std;
struct node
{
    
int num;
    
int value;

}
a[15];


int dp[100001];
int n,m;
int cash,N;


int main ()
{
    
int i,j,k;
    
while(scanf("%d%d",&cash,&N)!=EOF)
    
{

        memset(dp,
0,sizeof(dp));
        
for(i=1;i<=N;i++)
            scanf(
"%d%d",&a[i].num,&a[i].value);
        
for(i=1;i<=N;i++)
        
{

            
for(j=1;j<=a[i].num;j++)
            
{

                
for(k=0;k<=cash;k++)
                    
if(k+a[i].value<=cash&&dp[a[i].value+k]<a[i].value+dp[k])
                    
{
                        dp[a[i].value
+k]=a[i].value+dp[k];
                    }


            }

        }

        
int max=0;
        
for(i=0;i<=cash;i++)
            
if(dp[cash]>max)
                max
=dp[cash];
        printf(
"%d\n",max);

    }

}





后来思考了一下,把能想到的剪枝方法都用上了,不过还是。。。
虽然这个方法TLE了,不过还是值得说一下,里面
        if (cash==0||N==0)
        
{
            printf(
"0\n");
            
continue;
        }
必须放在输入之后,因为cash为0的时候N不一定为0;这时后面应该有读入的操作,如果不加处理会造成程序异常;
另外此处还添加了排序,貌似可以提高一点速度;

#include <iostream>
#include
<cstdio>
#include
<cmath>
#include
<algorithm>
using namespace std;
struct node
{

    
int num;
    
int value;

}
a[15];

int compare(const void* e1,const void* e2)
{
    node
* a = (node*)e1;
    node
* b = (node*)e2;
    
return b->value - a->value;
}



int dp[100001];
int n,m;
int cash,N;


int main ()
{
    
int i,j,k;
    
while(scanf("%d%d",&cash,&N)!=EOF)
    
{
    

        memset(dp,
0,sizeof(dp));
        
for(i=1;i<=N;i++)
            scanf(
"%d%d",&a[i].num,&a[i].value);
        
if (cash==0||N==0)
        
{
            printf(
"0\n");
            
continue;
        }

        qsort(a
+1,N,sizeof(a[1]),compare);
        
for(i=1;i<=N;i++)
        
{

            
for(j=1;j<=a[i].num;j++)
            
{

                
for(k=cash;k>=a[i].value;k--)
                
{
                    
if(dp[k]<dp[k-a[i].value]+a[i].value)
                        dp[k]
=dp[k-a[i].value]+a[i].value;



                }


            }

        }

        
int maxnum=0;
        
for(i=0;i<=cash;i++)
            
if(dp[i]>maxnum)
                maxnum
=dp[i];
        printf(
"%d\n",maxnum);

            

    }

    



}


最后才是AC的代码:
这个代码的优点在于含有状态转移方程的部分,它用max变量框定搜索的区间范围(初始值为0),对可以达到的cash值用ture标定后,再取最大的那个数更新max,这样最大限制的减少变量搜索的范围,节约了很多时间,强~

#include <iostream>
#include
<cstdio>
#include
<cmath>
#include
<algorithm>
using namespace std;


struct node
{

    
int num;
    
int value;

}
a[15];




bool dp[100001];
int cash,N;


int main ()
{
    
int i,j,k;
    
while(scanf("%d%d",&cash,&N)!=EOF)
    
{


        memset(dp,
0,sizeof(dp));
        
for(i=1;i<=N;i++)
            scanf(
"%d%d",&a[i].num,&a[i].value);
        
if (cash==0||N==0)
        
{
            printf(
"0\n");
            
continue;
        }


        
int max=0;
        dp[
0]=true;
        
for(i=1;i<=N;i++)
        
{
            
if(a[i].value>cash)
                
continue;
            
for(j=max;j>=0;j--)
            
{
                
if(dp[j]==true)
                
for(k=1;k<=a[i].num;k++)
                
{
                

                    
{
                        
int temp=j+k*a[i].value;
                        
if(temp>cash)
                            
break;
                        
if(temp>max)
                        
{
                            max
=temp;
                            
                        }

                        dp[temp]
=true;
                    }

                }

            }

        }

        printf(
"%d\n",max);

    }

    
return 0;
}





 

posted on 2009-02-20 17:46 abilitytao 阅读(2427) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理