TEL,DFS求剪枝!

2019.02.14

以下是代码:

#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个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

https://m.teaku.com/20/1550149010214223.html

最佳回答

首先,同志,这是一个动态规划,如果你真要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;

}

相关搜索