《算法笔记》dfs

图片.png

#include<cstdio>
const int maxn=30;
int n,V,maxValue=0;
int w[maxn],c[maxn];

void dfs(int index,int sumW,int sumC){
    //sumW总重量，sumC总价值 
    if(index==n){
        if(sumW<=V&&sumC>maxValue){
            maxValue=sumC;
        }
        return ;
    }
    //岔道口 
    dfs(index+1,sumW,sumC);//不选index件物品 
    dfs(index+1,sumW+w[index],sumC+c[index]);//选第index件物品 
}
int main(){
    scanf("%d%d",&n,&V);
    for(int i=0;i<n;i++){
        scanf("%d",&w[i]);//每件物品重
    }
    for(int i=0;i<n;i++){
        scanf("%d",&c[i]);//价值 
    }
    dfs(0,0,0);
    printf("%d\n",maxValue);
    return 0;
}

结果显示

优化：

图片.png

#include<cstdio>
const int maxn=30;
int n,V,maxValue=0;
int w[maxn],c[maxn];

void dfs(int index,int sumW,int sumC){
    //sumW总重量，sumC总价值 
    if(index==n)
    { 
        return ;//已经完成对所有物品的选择 
    }
    
    dfs(index+1,sumW,sumC);//不选index件物品 
    //只有加入第INDEX件物品后未超过容量V才可以继续
    if(sumW+w[index]<=V){
        if(sumC+c[index]>maxValue){
        maxValue=sumC+c[index];//更新最大价值 
    } 
    dfs(index+1,sumW+w[index],sumC+c[index]);//选第index件物品 
    }
}
int main(){
    scanf("%d%d",&n,&V);
    for(int i=0;i<n;i++){
        scanf("%d",&w[i]);//每件物品重
    }
    for(int i=0;i<n;i++){
        scanf("%d",&c[i]);//价值 
    }
    dfs(0,0,0);
    printf("%d\n",maxValue);
    return 0;
}

再改动，保存最大平方和的方案：

int n,k,x,maxSumSqu=-1,A[maxn];
int sumSqu=0;
vector<int>temp,ans;//存放当前已经选择的整数 
//sumSqu当前已选整数平方和，sum当前已选整数 
void dfs(int index,int nowK,int sum,int sumSqu){
    if(nowK==k&&sum==x){
        if(sumSqu>maxSqu){
            maxSumSqu=sumSqu;//更新最大平方和 
            ans=temp;//更新最优方案 
        }
        return ;
    }
    //已经处理完n个数，或者超过n个数，或者和超过x，返回 
    if(index==n||nowK>k||sum>x)return ;
    //选index号数
    temp.push_back(A[index]);
    dfs(index+1,nowK+1,sum+A[index],sumSqu+A[index]*A[index]);
    temp.pop_back();
    //不选
    dfs(index+1,nowK,sum,sumSqu); 
}