今天又做了一個背包的題目，有點郁悶~如果單純只考算法的話應該是很容易的，可是由于數據范圍太大，一直都過不了。。。汗~
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;
}