c++-下面的代碼dfs剪枝的if語句是什麼意思？？？？

下面的代碼dfs剪枝的if語句是什麼意思？？？？

描述
小珂最近收集了些郵票，他想把其中的一些給他的好朋友小明。每張郵票上都有分值，他們想把這些郵票分成兩份，並且使這兩份郵票的分值和相差最小（就是小珂得到的郵票分值和與小明的差值最小），現在每張郵票的分值已經知道了，他們已經分好了，你知道最後他們得到的郵票分值和相差多少嗎？

 #include <stdio.h>
#define max(a,b) a>b?a:b
int V,ans,n,w[110],sum[110];
void dfs(int i,int cnt)
{
if(i == 0)
{
ans = max(ans,cnt);
return ;
}
if(ans == V || cnt+sum[i] <= ans)       //cut
return ;
if(cnt+w[i] <= V)
dfs(i-1,cnt+w[i]);
dfs(i-1,cnt);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ans = 0;
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
sum[i] = sum[i-1] + w[i];
}
V = sum[n]/2;
dfs(n,0);
printf("%d\n",sum[n]-2*ans);
}
return 0;
}

最佳回答：

#include
#define max(a,b) a>b?a:b
int V,ans,n,w[110],sum[110];
//V是所有票面和的一半
//ans是較小那堆郵票的和,即 ans<=V
//這個搜索算法主要是 從第n張到第1張做出選或不選的決定來求得一個最貼近平均值V的ans
void dfs(int i,int cnt)
{
if(i == 0)//已經搜索到了最後一層
{
ans = max(ans,cnt);
return ;
}
/*1,ans始終保存較小的那堆郵票之和,滿足ans <=V; 當ans==V時當然就不能在選了(再選擇會超過V)
2,sum[i]=w[1] + w[2] + ... + w[i]; cnt + sum[i] <= ans 意思是即使剩下的全選所得的和也只能 <= 上一次搜索所得的ans,再繼續搜索也無意義*/
if(ans == V || cnt+sum[i] <= ans) //cut
return ;
if(cnt+w[i] <= V)//這個條件控制了所選的郵票之和始終 <=V,即會導致ans<=V
dfs(i-1,cnt+w[i]);
dfs(i-1,cnt);
}

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ans = 0;
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
sum[i] = sum[i-1] + w[i];
}
V = sum[n]/2;
dfs(n,0);
printf("%d\n",sum[n]-2*ans);
}
return 0;
}