动态规划02

今天主要看一下经典的背包问题：

01背包Charm Bracelet

有N件物品和一个容积为M的背包。第i件物品的体积w[i] ，价值是d[i]。求解将哪些物品装入背包可使价值总和 最大。每种物品只有一件，可以选择放或者不放 (N<=3500,M <= 13000)

 example:
   总体积：6          物品数：4
   体积：  1    2    3     2
   价值：  4    6    12    7
   取舍：  1    0    1     1
 结果：23

我们设V[i][j]表示前i个物品，体积不超过j，取得的最大价值。于是：

            V[i][j] = max(V[i - 1][j], V[i - 1][j - w[i]]+d[i])//表示在满足不超过j的情况下，对第i个物品进行取舍

#include <iostream>
#include <algorithm>
#include <string.h>
usingnamespacestd;

int main() {
    int N,M;
    cin>>N>>M;
    int W[N + 1],D[N + 1];//W是重量，D是期望度
    for (int i = 1; i <= N; i++) {
        cin>>W[i]>>D[i];
    }
    int MaxDesire[N + 1][M + 1];
    memset(MaxDesire, 0, sizeof(MaxDesire));
    for (int i = 1; i <= M; i++) {
        if (i >= W[1]) {
            MaxDesire[1][i] = D[1];
        } else MaxDesire[1][i] = 0;
    }
    for (int i = 2; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            MaxDesire[i][j] = MaxDesire[i - 1][j];
            if (j - W[i] >= 0) {
                MaxDesire[i][j] = max(MaxDesire[i - 1][j - W[i]] + D[i], MaxDesire[i - 1][j]);
            }
        }
    }
    cout<<MaxDesire[N][M];
    return0;
}

但是，这个题目如果这么开二维数组的话，就会超内存，我们得想一种更节省内存的办法。
即考虑：对这些物品而言，不超过j能达到的最大价值，我们设成MaxV[j]。动态规划，要求无后效性，而对前i种物品考虑的取舍，对i种以后的物品取舍，有无后效性（对比，三角形那的滚动数组）

#include <iostream>
#include <algorithm>
#include <string.h>
usingnamespacestd;

int main() {
    int N,M;
    cin>>N>>M;
    int W[N + 1],D[N + 1];//W是重量，D是期望度
    for (int i = 1; i <= N; i++) {
        cin>>W[i]>>D[i];
    }
    int MaxDesire[M + 1];
    memset(MaxDesire, 0, sizeof(MaxDesire));
    for (int i = 1; i <= N; i++) {
        for (int j = M; j >= W[i]; j--) {
            MaxDesire[j] = max(MaxDesire[j - W[i]] + D[i], MaxDesire[j]);
        }
    }
    cout<<MaxDesire[M]<<endl;
    return0;
}

神奇的口袋

神奇的口袋(百练2755)

有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。
John现在有n(1≤n ≤ 20)个想要得到的物品，每个物品的体积分别是a1，a2......an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式
  这道题有两种解法，一种是传统的递归式解法，另外一种是可达型动态规划，设计更加巧妙一些，当作练习题。【Tips:一维动规】
  我们设Ways[i][j]表示用前j件物品凑出i体积的方法数，而题目要求我们求的就是Ways[40][N],那么：

    *  如果前j-1件物品可以组成i, 那么前j件物品也可以组成i
    *  如果前j-1件物品可以组成i-a[j](所以必须是i-a[i]大于零的情况)，那么前j件物品也可以组成i

#include <iostream>
#include <algorithm>
#include <string.h>
usingnamespacestd;

int main() {
   int t;
   cin>>t;
   int A[t];
   int Ways[41][t + 1];
   memset(Ways, 0, sizeof(Ways));
   for (int i = 0; i < t; i++) {
       cin>>A[i];
   }
   for (int i = 0; i <= t; i++) {
       Ways[0][i] = 1;
   }
   for (int i = 0; i <= 40; i++) {
       for (int j = 1; j <= t; j++) {
           Ways[i][j] = Ways[i][j - 1];
           if (i - A[j - 1] >= 0) {
               Ways[i][j] = Ways[i][j - 1] + Ways[i - A[j - 1]][j - 1];
           }
       }
   }
   for (int i = 0; i <= 40; i++) {
       for (int j = 0; j <= t; j++) {
           cout<<Ways[i][j]<<" ";
       }
       cout<<i<<endl;
   }
   cout<<Ways[40][t];
   return0;
}

练习题：

用一维动规解决神奇的口袋
最佳加法表达式(百练上的版本要求高精度)