C++ 實現01背包動態規劃

簡述一下01背包：

背包容量大小固定，有一些物品，每個物品都有重量和價值兩個屬性，且物品唯一不重復（即同一物品只能放入一個），放入物品的總重量不能超過背包容量 ，求放入背包的物品的總價值最大化。0代表不放入，1代表放入。

可以通過建表的方式實現01背包，非遞歸實現。

如果用c[i]表示 i 號物品的重量，v[i]表示 i 號物品的價值，函數f（i，j）表示在有0,1,2...i 號物品和重量限制 j 時能夠得到的最大價值，表result[i][j]=f(i,j)

那麼可以f(i,j)=max((result[i - 1][j - c[i]] + v[i]),(result[i - 1][j]))查表非遞歸。

考慮如下：

有一個物品，我們需要考慮該不該把他放入背包中，無非放入和不放入兩種情況，那麼我們只需要把兩種情況下的總價值都算出來，然後取較大的一個就可以了。

result[i - 1][j - c[i]] + v[i]：放入的情況

總價值為 有 i-1 個物品且重量上限為當前上限 j 減去 i 號物品的重量時的價值 result[i - 1][j - c[i]] 加上 i 號物品的價值 v[i]

result[i - 1][j]：不放入的情況，總價值和 i-1 個物品時一樣（當前考慮的物品是 i 號物品）

代碼部分：

#include<iostream>
#include<string>
using namespace std;
int c[11]; //重量
int v[11]; //價值
int result[11][1001]; //表

///f()函數，計算在i+1個物品和重量上限j的條件下的最大背包價值

int f(int i,int j) //第i個物品，重量上限j  //0號物品即第一個物品
{
    if (i == 0&&c[i]<=j) //0號物品且重量小於上限
    {
        return v[i]; //把0號物品放入背包，背包價值為第0號物品的價值
    }
    if (i == 0 && c[i] > j)  //0號物品且重量大於上限
    {
        return 0; //物品放不進背包，此時背包為空，背包價值為0
    }

    //不是0號物品的情況
    if (i != 0 && j-c[i] >= 0) //i號物品可以放入背包
    {
        //判斷放入和不放入兩種情況下背包的價值，選擇價值大的方案
        return (result[i - 1][j - c[i]] + v[i]) > result[i - 1][j] ? (result[i - 1][j - c[i]] + v[i]) : result[i - 1][j];
    }          //把這個物品放入背包                //不放入背包
    else //i號物品不可以放入背包
    return  result[i - 1][j];
}

int getResult(int top, int num)
{
    if (num == 0) //有0個物品
        return 0;

    else
    {
       
        for (int i = 0; i < num; i++) //第i個物品
        {
            for (int j = 0; j <= top; j++) //重量
            {
                result[i][j] = f(i,j); //建表，result[i][j]表示有0,1,2...i個物品和j的重量限制下的最大背包價值
            }
        }
        return result[num-1][top];
    }
}

int main()
{
    int top; //背包容量
    int num; //物品數量
    cout << "輸入格式：上限，數量，每個物品的重量和價值。" << endl;
    cin >> top;
    cin >> num;
    for (int i = 0; i < num; i++) //第i個物品的重量和價值
    {
        cin >> c[i] >> v[i];
    }
    cout << getResult(top, num) << endl;
    return 0;
}

測試樣例1：

測試樣例2：

測試樣例3：