今天又做了一个背包的题目,有点郁闷~如果单纯只考算法的话应该是很容易的,可是由于数据范围太大,一直都过不了。。。汗~
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;
}

