實驗題目：0-1背包問題

問題描述：

面對每個物品，我們只有選擇拿取或者不拿兩種選擇，不能選擇裝入某物品的一部分，也不能裝入同一物品多次。

算法分析：

解決辦法：聲明一個 大小為 m[n][c] 的二維數(shù)組，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循環(huán)，外層for循環(huán)用來控制第i個物品，內(nèi)層for循環(huán)用來控制當前背包的容量多少，所以算法的總的復雜度為：O(n*c).

實驗總結(jié)：

本次實驗主要還是練習了動態(tài)規(guī)劃算法，解決的是0-1背包的問題，這是動態(tài)算法中比較基礎(chǔ)較簡單的一種，因此掌握該算法可以為以后更好的理解其他更深入的算法打好堅實的基礎(chǔ)。該算法通過構(gòu)造子問題的最優(yōu)子結(jié)構(gòu)，然后將大規(guī)模的問題一步一步的進行細化，不斷地轉(zhuǎn)化為規(guī)模更加小的子問題，通過子問題的求解，最終求出原問題的解。是一個自底向上不斷求解的過程。

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