🎵二維費(fèi)用背包問題

🎶引言

背包問題是算法中的經(jīng)典問題之一，其變種繁多。本文將介紹二維費(fèi)用背包問題及其解決方案。

🎶問題定義

二維費(fèi)用背包問題可以描述為：給定 (N) 個(gè)物品，每個(gè)物品有兩個(gè)費(fèi)用和一個(gè)價(jià)值，在兩種費(fèi)用的限制下，如何選擇物品使得總價(jià)值最大。

🎶動(dòng)態(tài)規(guī)劃思想

動(dòng)態(tài)規(guī)劃是解決背包問題的常用方法。通過定義合適的狀態(tài)和狀態(tài)轉(zhuǎn)移方程，我們可以有效地解決二維費(fèi)用背包問題。

🎶狀態(tài)定義和狀態(tài)轉(zhuǎn)移方程

我們定義 dp[i][j][k] 表示前 i 個(gè)物品在費(fèi)用1不超過 j 和費(fèi)用2不超過 k 的情況下的最大價(jià)值。狀態(tài)轉(zhuǎn)移方程為：

$dp[i][j][k]=\max (dp[i?1][j][k],dp[i?1][j?cost1[i]][k?cost2[i]]+value[i])$

🎶初始條件和邊界情況

初始條件為 dp[0][j][k] = 0，表示沒有物品時(shí)的最大價(jià)值為 0。邊界條件需要根據(jù)實(shí)際問題進(jìn)行處理。

🎵例題

🎶1.一和零

題目：

樣例輸出和輸入：

算法原理：
這道題就是讓我們找子集的長(zhǎng)度，這個(gè)子集滿足：當(dāng)中的0不大于m個(gè)，當(dāng)中的1不大于n個(gè)，最后返回最大的子集的長(zhǎng)度，所以我們首先想到的是二維費(fèi)用背包問題，因?yàn)橛袃蓚€(gè)限制，這里的背包的限制就是0和1的個(gè)數(shù)的限制，這里的物品其實(shí)就是每個(gè)字符串。
狀態(tài)表示：$dp[i][j][k]$表示從前$i$個(gè)物品中選擇的所有組合中，滿足0的個(gè)數(shù)不大于m，1的個(gè)數(shù)不大于n個(gè)的所有組合中子集長(zhǎng)度最大的那個(gè)的長(zhǎng)度。
狀態(tài)轉(zhuǎn)移方程：

這里的a和b代表的是當(dāng)前i位置字符串中0和1分別的個(gè)數(shù)，所以我們?cè)谶M(jìn)行填表的時(shí)候應(yīng)該遍歷一下字符串，將當(dāng)中的0和1分別記錄一下，狀態(tài)轉(zhuǎn)移方程：

$dp[i][j][k]=max(dp[i?1][j][k],dp[i?1][j?a][k?b])$

初始化：

代碼：
未優(yōu)化的代碼：

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n){int sz = strs.size();vector<vector<vector<int>>> dp(sz + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));for (int i = 1;i <= sz;i++){//統(tǒng)計(jì)一下字符串中0和1的個(gè)數(shù)int a = 0, b = 0;for (auto e : strs[i - 1]){if (e == '1')b++;else a++;}for (int j = 0;j <= m;j++){for (int k = 0;k <= n;k++){dp[i][j][k] = dp[i - 1][j][k];if (j >= a && k >= b)dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - a][k - b] + 1);}}}return dp[sz][m][n];}
};

滾動(dòng)數(shù)組優(yōu)化的代碼：

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n){int sz = strs.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));for (int i = 1;i <= sz;i++){//統(tǒng)計(jì)一下字符串中0和1的個(gè)數(shù)int a = 0, b = 0;for (auto e : strs[i - 1]){if (e == '1')b++;else a++;}for (int j = m;j >=a;j--)for (int k = n;k >=b;k--)dp[j][k] = max(dp[j][k], dp[j - a][k - b] + 1);}return dp[m][n];}
};

運(yùn)行結(jié)果：

🎶2.盈利計(jì)劃

題目：

樣例輸出和輸入：

算法原理：
這道題每個(gè)group對(duì)應(yīng)一個(gè)profit，下標(biāo)是對(duì)應(yīng)的。

根據(jù)上面的圖片加上題目要求，我們可以得知，我們每次選擇的利潤(rùn)必須大于給定的$minProfit$然后每次需要的人口不能超過$n$，最后求出滿足這個(gè)條件的所有組合有多少種。
狀態(tài)表示：$dp[i][j][k]$表示從前i個(gè)工作計(jì)劃中選擇，人數(shù)不超過i的，但是盈利大于k的所有組合數(shù)的總和。
狀態(tài)轉(zhuǎn)移方程：
第一種狀態(tài)：不選擇i位置，$dp[i?1][j][k]$

第二種狀態(tài)：選擇i位置，首先考慮二維$dp[i?1][j?group[i]]$這里我們考慮一下$j?group[i]\le 0$是否成立將group[i]移到右邊去可以得到：$j\le group[i]$這個(gè)是什么意思呢？表示i工作需要的人口是大于總?cè)丝趈的，所以這肯定是不可能的，所以這里中只能是$j?group[i]\ge 0$，我們?cè)賮砜紤]三維的：$dp[i?1][j?group[i]][k?profit[i]]$我們來考慮$k?profit[i]\le 0$是否成立，首先我們還是繼續(xù)移一下項(xiàng)：$k\le profit[i]$這里k表示總的利潤(rùn)，profit表示當(dāng)前工作產(chǎn)出的利潤(rùn)，所以這里的意思就表示無論前面總利潤(rùn)是多少，這里都都能滿足當(dāng)前的利潤(rùn)，所以我們只需要選擇0即可，所以第二種狀態(tài)：

$dp[i?1][j?group[i]][max(0,k?profit[i])]$

最后這兩種狀態(tài)的總和就是當(dāng)前狀態(tài)的所有組合的總和：

$dp[i][j][k]=dp[i?1][j][k]+dp[i?1][j?group[i]][max(0,k?profit[i])]$

代碼：
未優(yōu)化的代碼：

class Solution {
public:int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {int len = group.size();int MOD = 1e9 + 7;vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));for (int j = 0;j <= n;j++){dp[0][j][0] = 1;}for (int i = 1;i <= len;i++){for (int j = 0;j <= n;j++){for (int k = 0;k <= minProfit;k++){dp[i][j][k] = dp[i - 1][j][k];if (j >= group[i-1])dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];dp[i][j][k] %= MOD;}}}return dp[len][n][minProfit];}
};

優(yōu)化過后的代碼：

int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) 
{int len = group.size();int MOD = 1e9 + 7;vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));for (int j = 0;j <= n;j++)dp[j][0] = 1;for (int i = 1;i <= len;i++)for (int j = n;j >= group[i - 1];j--)for (int k = 0;k <= minProfit;k++){dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])];dp[j][k] %= MOD;}return dp[n][minProfit];
}

運(yùn)行結(jié)果：

🎵總結(jié)

通過本文的學(xué)習(xí)，我們了解了二維費(fèi)用背包問題的基本概念和解決方法。與傳統(tǒng)的單一費(fèi)用背包問題不同，二維費(fèi)用背包問題在解決時(shí)需要同時(shí)考慮兩種費(fèi)用的限制，這使得問題更具挑戰(zhàn)性，但也更貼近實(shí)際應(yīng)用場(chǎng)景。我們通過動(dòng)態(tài)規(guī)劃的方法，逐步構(gòu)建狀態(tài)轉(zhuǎn)移方程，并利用二維數(shù)組來存儲(chǔ)中間結(jié)果，從而實(shí)現(xiàn)了對(duì)問題的高效求解。

在實(shí)際應(yīng)用中，掌握二維費(fèi)用背包問題的解決思路，可以幫助我們?cè)谫Y源分配、投資組合等多方面優(yōu)化決策。希望通過本次的學(xué)習(xí)，大家不僅能夠掌握相關(guān)的算法技巧，還能夠舉一反三，靈活應(yīng)用于更多復(fù)雜的優(yōu)化問題中。

今后，我們將繼續(xù)探討更為復(fù)雜的動(dòng)態(tài)規(guī)劃問題，進(jìn)一步提升算法設(shè)計(jì)和問題求解能力。謝謝大家的閱讀，希望本文對(duì)你有所幫助。