TEL，DFS求剪枝！

更新时间：2019-02-17 05:16:58 137次访问

以下是代码：

#include<iostream>

#include<cmath>

using namespace std;

int m,n,ans=20001,a[31],c[31]={0};

void dfs(int i,int sum){

if(sum>=n||i>m){

if(sum>n&&n-sum+a[i-1]<ans) ans=n-sum+a[i-1];

else if(sum==n) ans=0;

else if(sum<n&&n-sum<ans) ans=n-sum;

return ;

}

else for(int j=1;j<=m;j++)

if(!c[j]){

c[j]++;

dfs(i+1,sum+a[j]);

c[j]--;

sum-=a[j];

}

return ;

}

int main(){

cin>>n>>m;

for(int i=1;i<=m;i++) cin>>a[i];

dfs(1,0);

cout<<ans;

return 0;

}

有一个箱子容量为VV（正整数，0 le V le 200000≤V≤20000），同时有nn个物品（0<n le 300<n≤30，每个物品有一个体积（正整数）。

要求nn个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

首先，同志，这是一个动态规划，如果你真要dfs剪枝，那么：

1：ans=0可以直接一路return;

2：c数组可以不用，只要确保是从1~m

3：ans初值应赋值为n。

我是这么写的：

#include<iostream>

#include<cmath>

using namespace std;

int m,n,ans,a[31];

void dfs(int i,int sum) {

    if(i>m) {

        ans=min(ans,n-sum);

        return ;

    } else {

    if(a[i]+sum<=n)dfs(i+1,sum+a[i]);

    dfs(i+1,sum);

}

    return ;

}

int main() {

    cin>>n>>m;

    for(int i=1; i<=m; i++) cin>>a[i];

    ans=n;

    dfs(1,0);

    cout<<ans;

    return 0;

}