TEL,DFS求剪枝!

6个月前

以下是代码:

#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;

    }

相关搜索