动态规划---0-1 sack

实验题目：0-1背包问题

问题描述：

面对每个物品，我们只有选择拿取或者不拿两种选择，不能选择装入某物品的一部分，也不能装入同一物品多次。

算法分析：

解决办法：声明一个 大小为 m[n][c] 的二维数组，m[i][j] 表示 在面对第 i 件物品，且背包容量为 j 时所能获得的最大价值 ，那么我们可以很容易分析得出 m[i][j] 的计算方法，
（1） j < w[i] 的情况，这时候背包容量不足以放下第 i 件物品，只能选择不拿
m[ i ][ j ] = m[ i-1 ][ j ]
（2） j > = w[i] 的情况，这时背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。
如果拿取，m[ i ][ j ]=m[ i-1 ][ j-w[ i ] ] + v[ i ]。 这里的m[ i-1 ][ j-w[ i ] ]指的就是考虑了i-1件物品，背包容量为j-w[i]时的最大价值，也是相当于为第i件物品腾出了w[i]的空间。
如果不拿，m[ i ][ j ] = m[ i-1 ][ j ] , 同（1）
究竟是拿还是不拿，自然是比较这两种情况那种价值最大。

例子：6个物品，（重量，价值）分别为：（4，8），（6，10），（2，6），（2，3），（5，7），（1，2）。
背包容量 0 1 2 3 4 5 6 7 8 9 10 11 12
物品1 0 0 0 0 8 8 8 8 8 8 8 8 8
物品2 0 0 0 0 8 8 10 10 10 10 18 18 18
物品3 0 0 6 6 8 8 14 14 16 16 18 18 24
物品4 0 0 6 6 9 9 14 14 17 17 19 19 24
物品5 0 0 6 6 9 9 14 14 17 17 19 21 24
物品6 0 2 6 8 9 11 14 16 17 19 19 21 24

程序清单

#include <iostream> 
#include <cstring>
using namespace std;

const int N = 15;
int m[N][N];

int maxiu(int a, int b)
{
    return (a > b) ? a:b;
}

void KnapSack(int n,int c,int w[],int v[])
{
    int i,j;
    for(i = 1;i <= n; i++){
        for(j = 1; j <= c; j++){
            if(j >= w[i]){
                m[i][j] = max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
            }
            else{
                m[i][j] = m[i-1][j];
            }
        } 
    } 
}

void printArray(int n,int c)
{
    int i , j;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= c; j++){
            cout << m[i][j] << " ";
        }
        cout << endl;
    }
}
int main()
{
    int v[N] = {0,8,10,6,3,7,2};
    int w[N] = {0,4,6,2,2,5,1};
    int n = 6, c = 12;
    memset(m,0,sizeof(m));
    KnapSack(n,c,w,v);
    printArray(n,c);
    return 0;
}

复杂度分析：

    //该算法核心部分为：

    for(i = 1;i <= n; i++){
        for(j = 1; j <= c; j++){
            if(j >= w[i]){
                m[i][j] = max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
            }

该算法的核心部分为两层for循环，外层for循环用来控制第i个物品，内层for循环用来控制当前背包的容量多少，所以算法的总的复杂度为：O(n*c).

实验总结：

本次实验主要还是练习了动态规划算法，解决的是0-1背包的问题，这是动态算法中比较基础较简单的一种，因此掌握该算法可以为以后更好的理解其他更深入的算法打好坚实的基础。该算法通过构造子问题的最优子结构，然后将大规模的问题一步一步的进行细化，不断地转化为规模更加小的子问题，通过子问题的求解，最终求出原问题的解。是一个自底向上不断求解的过程。

You can leave me a message if you find out any mistake in my diary, I'll correct it, thanks.