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