算法 -- 0-1背包問題之動态規劃

本來周五要完成0-1背包問題,由于自己的某些事情耽擱.以後要嚴格要求自己喽!!! 下面我們一起來學習0-1背包問題:

問題描述:

有N件物品和一個容量為c的背包。第i件物品的重量是w[i]，價值是v[i]。求解将哪些物品裝入背包可使價值總和最大。之是以稱為”0-1背包問題”表示該問題隻有兩種結果:裝或者不裝即0或者1.

基本思路:

該問題中,每一種物品隻有一件,同時選擇隻有放和不放.

實作過程需要借助一個二維數組m[N+1][c+1],m[i][j]表示i号物品在容量為j時,放或者不放入時的最大價值.

我采用的是從最後一個物品開始分析,即從下至上分析.

首先給出一組資料:

總共物品數目:N=5 背包容量:c = 10

每個物品的重量w[6] = { 0 , 2 , 2 , 6 , 5 , 4 }

每個物品的價值v[6] = { 0 , 6 , 3 , 5 , 4 , 6 }

定義數組m[6][11]:

其中第0位，置為0，不參與計算，隻是便于與後面的下标進行統一，無特别用處，也可不這麼處理。因為物品總數為5,背包的最大容量為10，那麼在設定數組m大小時，可以設行列值為6和11，那麼，對于m(i,j)就表示可選物品為i…n背包容量為j(總重量)時背包中所放物品的最大價值。

過程分析:

1.首先背包初始是空的,任何一個物品都沒有裝入.

2.我們從最後一個物品開始分析,即在重量為0~10時,如何放置物品n,使其中價值最大,此時需要确定m[5][0~10]這11個元素的值.

如果物品的重量w[5]大于目前背包的剩餘容量j,則背包不能放入該物品,即此時價值為m[5][j]=0;否則可以放入該物品,即此時價值為該物品的價值v[5].

3.接下來我們來分析前n-1個物品在j=0~10的情況下是否放入背包.此時每一個物品的分析都是建立在上一個物品的基礎上的,以4号物品為例:

m[4][0~10]這11個值的确定,需要建立在5号物品的基礎上.同樣分為兩種情況:第一種w[4]>j,則背包不能裝入該物品,是以此時的最大價值為上一個物品的在j值下對應的值即m[4][j]=m[5][j];第二種w[4]<=j,則背包可以放入該物品,此時就需要比較放入後的價值大,還是不放的價值大.

4.和4号物品的分析方法一樣,完成剩下的物品在m數組中的對應值.

總結來講就是:

w[i]>j,則m[i][j]=m[i+1][j];

w[i]<=j, 則m[i][j]=max ( m[i+1][j] , v[i]+m[i+1][j-w[i]]).

以上内容綜合起來表達如下圖所示:

實作的代碼如下:

/*************************************************************************
 **     >  Name : 0_1.c
 **     > Author: LiYingXiao (Sweethreart502) 
 **     >  Mail : [email protected]
 **     >  Blog : http://blog.csdn.net/u013166575
 **     > Created Time: 2015年11月21日 星期六 23時41分19秒
 ************************************************************************/

#include <stdio.h>

// 五個物品的對應重量
int w[] = {  ,  ,  ,  ,  ,  } ;
// 五個物品的對應價值
int v[] = {  ,  ,  ,  ,  ,  } ;
// 背包總容量
int c =  ;
// 每一個物品的狀态值
int x[] = {  } ;


// 核心處理函數
void process ( int m[][] ) ;

// 輸出放入情況
void option ( int m[][] )  ;

int main ( int argc , char * argv[] )
{
    int i ;

    // 初始化價值數組為0
    int m[][] = {  } ;

    process ( m ) ;

    option ( m ) ;

    // 輸出情況
    for ( i =  ; i <=  ; i++ ) {
        if ( x[i] ) {
            printf ( "1  " ) ;
        } else {
            printf ( "0  " ) ;
        }
    }
    printf ( "\n" ) ;

    return  ;
}

void process ( int m[][] )
{
    int i , j ;

    /* 首先解決最後一個物品是否放入 */
    for ( j =  ; j <= c ; j++ ) {
        if ( w[] > j ) {
            m[][j] =  ; 
        } /* 不能放下,價值為零 */
        else {
            m[][j] = v[] ;
        }/* 可以放下,價值為其本身價值 */
    }

    /* 從下至上分析 */
    for ( i =  ; i >=   ; i-- ) { /* 從下至上依次分析每一個物品 */
        for ( j =  ; j <= c ; j++ ) { /* 從左至右一次分析j在0~10之間 */
            if ( w[i] > j ) { 
                m[i][j] = m[i+][j] ;
            } /* 不能放入,則價值為下一行同一列的值 */
            else {
                m[i][j] = ( m[i+][j] > v[i]+m[i+][j-w[i]] ) ? m[i+][j] : v[i]+m[i+][j-w[i]] ;
                /* 如果放入,則它的價值為目前物品的價值加上下一個物品在剩餘容量j減去目前物品重量的條件下的價值 */
            } /* 分析放入的價值大,還是不放的價值大 */
        }
    }
}

void option ( int m[][] ) 
{
    int i , j = c ; 

    /* 初識情況将j設定為c總容量 */
    for ( i =  ; i <=  ; i++ ) {
        if ( m[i][j] == m[i+][j] ) {
            /* 如果該物品價值與下一個物品在目前j下的價值相等,則該物品未放入.因為m數組初始情況是從下到上分析的 */
            x[i] =  ;
        } 
        else {
            x[i] =  ;
            j -= w[i] ; /* 放入某物品後,要将j減少該物品的重量 */
        }
    }
    /* 最後一個物品是否放入,隻需要看目前物品在j下是否價值為零. */
    x[] = m[][j] ?  :  ;
} 
           

思考:

如果再添加一個限制條件總體積小于等于t,應該如何實作?

其實和二維的解決方法類似,就相當于數學上面的”同理可得”一樣.

代碼如下:

/*************************************************************************
 **     >  Name : wv_0_1.c
 **     > Author: LiYingXiao (Sweethreart502) 
 **     >  Mail : [email protected]
 **     >  Blog : http://blog.csdn.net/u013166575
 **     > Created Time: 2015年11月22日 星期日 09時32分45秒
 ************************************************************************/
/* 0_1問題的三維,即在兩個限制條件的限制下 */
#include<stdio.h>  
#include<stdlib.h>  
#include<iostream>  
#include<queue>  
#include<climits>  
#include<cstring>  

using namespace std;  

// 背包總容量
int c =  ;
// 背包總體積
int t =  ;
// 每一個物品的重量
int w[] = {  ,  ,  ,  ,  } ;  
// 每一個物品的體積
int s[] = {  ,  ,  ,  ,  } ;
// 每一個物品的價值
int v[] = {  ,  ,  ,  ,  } ;
// 物品的狀态
int x[];  


/* 0-1背包問題 */
void package0_1 ( int m[][][] )   
{  
    // 采用從底到頂的順序來設定m[i][j][k]的值  
    int i , j , k ;
    // 首先分析最後一個物品
    for ( j =  ; j <= c ; j++ ) {
        for ( k =  ; k <= t ; k++ ) {
            if ( w[] <= j && s[] <= k ) {
                /* 重量和體積同時滿足條件,則放入 */
                m[][j][k] = v[] ;
            } else {
                /* 任何一個不滿足,則不放入 */
                m[][j][k] =  ;
            }
        }
    }

    //對剩下的n-1個物品進行放置。  
    for( i =  ; i >=  ; i--) {
        for(int j =  ; j <= c ; j++) { 
            for ( k =  ; k <= t ; k++ ) {
                if ( w[i] <= j && s[i] <= k ) {
                    /* 重量和體積同時滿足條件 */
                    m[i][j][k] = ( m[i+][j][k] > v[i]+m[i+][j-w[i]][k-s[i]] ) ? m[i+][j][k] : v[i]+m[i+][j-w[i]][k-s[i]] ;
                }
                else {
                    m[i][j][k] = m[i+][j][k] ;
                }
            }
        }  
    }
}


void answer ( int m[][][] )
{  
    int i , j = c , k = t ;  

    // 周遊m數組,從第一個貨物周遊,判斷是否裝入
    for ( i =  ; i <=  ; i++ ) { 
        if ( m[i][j][k] == m[i+][j][k] ) { // 如果目前物品的價值與下一個物品價值相等,說明沒有裝i物品
            x[i] = ;  
        }
        else { // 否則裝進去
            x[i] = ;  
            j = j - w[i];  
            k = k - s[i] ;
        }      
    }
    // 如果n物品在目前剩餘容量j下非零,則表示裝入該物品
    x[] = m[i][j][k] ?  :  ;   
}

// 主函數
int main()  
{  
    // 5個物品,總重量為10,總體積為10
    // m數組分析中存儲剩餘空間為j時,目前的最大價值
    int m[][][]={};  // 初始化為0

    // 分析并存儲m數組
    package0_1 ( m ) ;  


    // 具體的裝載資訊
    answer(m);  

    // 輸出最優解
    cout << "The best answer is:\n";  
    for ( int i =  ; i <=  ; i++ ) { 
        cout << x[i] << " ";  
    }
    std::cout << std::endl ;

    return ;  
}