0-1背包問題動态規劃求解

題目描述： 有編号分别為a,b,c,d,e的五件物品，它們的重量分别是2,2,6,5,4，它們的價值分别是6,3,5,4,6，現在給你個承重為10的背包，如何讓背包裡裝入的物品具有最大的價值總和？

根據m[i][j]的遞推公式，背包中最大的價值總和為m[1][n]

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

int main()
{
    int n;//一共有n個物品
    int weight;//背包承重為weight
    cin>>n>>weight;
    int w[n+1];//用來表示每個物品的重量
    int v[n+1];//用來表示每個物品的價值
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i];
        
    int m[n+1][weight+1];
    //當背包容量為0時，背包能容納的最大價值量為0
    for(int i=0;i<=n;i++)
        m[i][0]=0;
    //初始條件，最後一行
    //如果背包裝不下第n個物品，m[n][j]=0
    //如果背包能夠裝下第n個物品，m[n][j]=v[n]
    for(int j=0;j<=weight;j++){
        if(j<w[n])
            m[n][j]=0;
        else
            m[n][j]=v[n];
    }
    //逆序填充二維數組m[i][j]
    for(int i=n-1;i>=1;i--)
    for(int j=1;j<=weight;j++)
    {
        if(j<w[i])
        //如果裝不下目前物品，即不裝目前物品，有m[i][j]=m[i+1][j]
            m[i][j]=m[i+1][j];
        else{
        //能夠裝下目前物品，比較裝下後剩餘背包容量所能容納最大價值量與目前物品價值量之和
        //與不裝目前物品的背包容納最大價值量之和
            if(m[i+1][j]>m[i+1][j-w[i]]+v[i])
                m[i][j]=m[i+1][j];
            else
                m[i][j]=m[i+1][j-w[i]]+v[i];
        }

    }
    //m[1][weight]即為最優解
    cout<<m[1][weight];
    return 0;
}
           

時間複雜度

算法複雜度分析：

從m(i，j)的遞歸式容易看出，算法需要O(nweight)計算時間。當背包容量weight很大時，算法需要的計算時間較多。例如，當weight>2n時，算法需要Ω(n2n)計算時間