[数据结构与算法]动态规划专项三

动态规划是非常值得训练的，结合了众多的算法思想在其中，例如递归、回溯、深搜等等。
前两次得动态都是非常容易的，比较能看出状态转移方程的，然而今天的2个经典算法有些难度。
动态规划专项一，点击此处
动态规划专项二，点击此处
这次专项是经典的算法问题，值得回味。

n皇后问题

不说了，这个问题还进了知乎，想看的可以点击此处
问题描述:说到这个N-皇后问题，就不得不先提一下这个历史上著名的8皇后问题啦。
八皇后问题，是一个古老而著名的问题.该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法?（根据程序有92种算法）
那么，我们将8皇后问题推广一下，就可以得到我们的N皇后问题了。N皇后问题是一个经典的问题，在一个NxN的棋盘上放置N个皇后，使其不能互相攻击 (同一行、同一列、同一斜线上的皇后都会自动攻击) 那么问，有多少种摆法？
这里给出摆法和总数。
关键算法就是判断(列+对角线)与深搜

#include <iostream>
#include <cmath>

using namespace std;

const int N=20;
int count=0;
int q[N];

bool find(int i,int j){
    int k=1;
    while(k<i){
        if(q[k]==j||abs(k-i)==abs(q[k]-j))
            return false;
        k++;
    }
    return true;
}

void print(int n){
    cout<<endl;
    count++;
    int i,j;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(q[i]!=j) cout<<"x ";
            else cout<<"Q ";
        }
        cout<<endl;
    }
}

void dfs(int k,int n){
    int j;
    if(k>n) print(n);
    else{
        for(j=1;j<=n;j++){
           if(find(k,j)){
               q[k]=j;
               dfs(k+1,n);
           }
        }
    }
}

int main(){
    int n;
    cin>>n;
    dfs(1,n);
    cout<<count<<endl;
    return 0;
}

这里以n=4为例输出样式。

0-1背包问题

问题描述：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
关键状态转移方程：dp[i][r]=max(dp[i-1][r],dp[i-1][r-w[i]]+v[i])
背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

多种背包问题链接，下次有时间更新。点击此处

#include <iostream>
#include <algorithm>
//#define max(x,y) ((x)>(y)?(x):(y))

using namespace std;

int n,w1;
int w[20];
int v[20];
int dp[20][100];
int x[20];
int maxv=0;

void knap(){
    int i,r;
    for(i=0;i<=n;i++) dp[i][0]=0;
    for(r=0;r<=w1;r++) dp[0][r]=0;
    for(i=1;i<=n;i++){
        for(r=1;r<=w1;r++){
            if(r<w[i]) dp[i][r]=dp[i-1][r];
            else dp[i][r]=max(dp[i-1][r],dp[i-1][r-w[i]]+v[i]);
        }
    }
}

void Build(){
    int i=n,r=w1;
    while(i>=0){
        if(dp[i][r]!=dp[i-1][r]){
            x[i]=1;
            maxv+=v[i];
            r=r-w[i];
        }
        i--;
    }
}

int main(){
    cin>>n>>w1;
    for(int i=0;i<=n;i++){
        cin>>v[i];
    }
    for(int j=0;j<=n;j++){
        cin>>w[j];
    }
    knap();
    Build();
    for(int k=0;k<=n;k++){
        if(x[k]==1){
            cout<<k<<" ";
        }
    }
    cout<<"\n"<<maxv<<endl;
    return 0;
}

结果运行图