今天又做了一個(gè)背包的題目，有點(diǎn)郁悶~如果單純只考算法的話應(yīng)該是很容易的，可是由于數(shù)據(jù)范圍太大，一直都過(guò)不了。。。汗~
TLE了2個(gè)小時(shí)，自己嘗試了N種剪枝方法但還是過(guò)不去。最后無(wú)奈只好到網(wǎng)絡(luò)上搜索了一下，借用了網(wǎng)上大牛代碼中的一個(gè)剪枝方法，才過(guò)掉這道題的。。。
剛開始的時(shí)候我是這么寫的，沒有任何剪枝，結(jié)果當(dāng)然是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);
}
}
后來(lái)思考了一下，把能想到的剪枝方法都用上了，不過(guò)還是。。。
雖然這個(gè)方法TLE了，不過(guò)還是值得說(shuō)一下，里面
if (cash==0||N==0)
{
printf("0\n");
continue;
}
必須放在輸入之后，因?yàn)閏ash為0的時(shí)候N不一定為0;這時(shí)后面應(yīng)該有讀入的操作，如果不加處理會(huì)造成程序異常；
另外此處還添加了排序，貌似可以提高一點(diǎn)速度；
#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的代碼：
這個(gè)代碼的優(yōu)點(diǎn)在于含有狀態(tài)轉(zhuǎn)移方程的部分，它用max變量框定搜索的區(qū)間范圍（初始值為0），對(duì)可以達(dá)到的cash值用ture標(biāo)定后，再取最大的那個(gè)數(shù)更新max,這樣最大限制的減少變量搜索的范圍，節(jié)約了很多時(shí)間，強(qiáng)~
#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;
}