简单的动态规划算法

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define maxn 15//对于100%的数据，n<=13

int n,similar[maxn][maxn];

int dp[maxn][1<<13];

bool legal(int i,int k){//前i个人是否能形成k这种情形，也就是k中的1的个数是否=i

    int numof1=0;

    while(k){

        if(k&1){

            numof1++;

        }

        k>>=1;

    }

    if(i==numof1)return 1;

    return 0;

}

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

            scanf("%d",&similar[i][j]);

        }

    }

    dp[0][0]=0;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

            for(int k=1;k<(1<<n);k++){

                if((k>>(j-1))&1&&legal(i,k)){//k对应的情况选了第j个人

                    dp[i][k]=max(dp[i][k],dp[i-1][k-(1<<(j-1))]+similar[i][j]);

                }

            }

        }

    }

    printf("%d",dp[n][(1<<n)-1]);

    //system("pause");

    return 0;

}