文章目錄
- 0-1背包問題
- 動態規劃標準套路
- 偽代碼
- 修繕代碼
- 子集背包問題
- 思路分析
- 代碼實作
- 完全背包問題
本來要拿《背包九講》作為參考的，奈何太抽象，我看不懂
0-1背包問題
給你一個載重量為 W 的背包，以及一堆物品，這些物品都有屬于自己的兩個屬性：價值var和質量wt，試問這個背包最多能裝多少價值的物品，
這里面的每一個物品，要么裝，要么不裝，
看到這個圖，第一反應是不是：性價比比一下，如果是這樣想的朋友可以停下來了，性價比不行，
如果只有兩個物品，一個4Kg，值8￥；一個15Kg，值10￥；很明顯前面那個性價比高，但是顯然我們要選的是后面這個，
這種題目，實在讓人很懵逼，就好像千頭萬緒，但是所有思路都被自己給否定了，
動態規劃標準套路
1、明確狀態和選擇
什么是狀態，就是背包的容量，以及可以選擇的物體，
什么是選擇，這個物品，要不要放進背包，
2、明確dp陣列
剛剛說到有兩個狀態，所以我們選用一個二維陣列：dp[i][w]：對于前 i 個物體，在背包容量為w的時候，可以裝的最大價值是dp[i][w]，
例：dp[3][5] = 6:對于前三個物體做選擇，在背包容量為5的時候，可以選擇的最大價值為6，
根據定義，我們的最終目標可以設為 dp[N][M]，
base case 就是dp[0][···] = 0，dp[···][0] = 0，沒有物品或者背包沒有空間的時候，能裝的最大價值就是0，
3、狀態轉移方程
對第i件物品來說，無非就是選中了，和沒選中嘛，
那么，
如果選中了：d[i][w] = d[i-1][w-wt[i-1]]+var[i]
如果沒選中：d[i][w] = d[i-1][w]
什么情況下要選？什么情況下不選呢？
那當然是哪個有利就選哪個嘛，
所以，偽代碼怎么寫？
偽代碼
int dp[N+1][W+1]
dp[0][···] = 0
dp[···][0] = 0
for i in range(1,N)：
for w in range(1,w):
dp[i][w] = max(裝，不裝)
//裝不裝的狀態轉移已經在上面了
return dp[N][W]
修繕代碼
int knaspsack(int W,int N,vector<int>& wt,vector<int>& val){
vector<vector<int>> dp(N+1,vector<int>(W+1,0));
for(int i = 1;i <= N; i++){
for(int w = 1;w <= W; w++){
if(w-wt[i-1]<0) //沒空間了
dp[i][w] = dp[i-1][w];
else
dp[i][w] = max(d[i-1][w-wt[i-1]]+var[i],dp[i-1][w]);
}
}
return dp[N][W];
}
子集背包問題
給你一個只包含正整數的陣列，設計一個演算法，將這個陣列分為兩個元素和相等的子集，如果能分，回傳true，如果不能分，回傳false，
這個問題怎么轉化為背包為題呢？
首先，對這個陣列計數，如果和是奇數，就回傳-1吧，如果和是偶數，就除于二，記為n，
這個問題就轉變為：從陣列中找出一些數，使得它們的和恰好等于n，
其實看了這個題目，最直接的想法就是逆序排序之后用回溯
思路分析
狀態和選擇已經很明確了吧，
dp陣列的含義嘛，dp[i][j] = x 表示，對于前 i 個物品，當前背包容量為 j 的時候，正好能將背包裝滿，則x為true，否則為false、
做一下狀態壓縮，把[i]去掉，反正i也是用來回圈的，
如果不把 nums[i] 裝入子集，則能夠恰好裝滿背包，取決于上一個狀態 dp[i-1][j]，繼承之前的結果，
如果把 nums[i] 裝入子集，則能否恰好裝滿背包，取決于狀態 dp[i-1][j-nums[i-1]]，
代碼實作
bool canPartition(vector<int>& nums) {
int sum = 0, n = nums.size();
for (int num : nums) sum += num;
if (sum % 2 != 0) return false;
sum = sum / 2;
vector<bool> dp(sum + 1, false);
// base case
dp[0] = true;
for (int i = 0; i < n; i++)
for (int j = sum; j >= 0; j--)
if (j - nums[i] >= 0)
dp[j] = dp[j] || dp[j - nums[i]];
return dp[sum];
}
完全背包問題
換零錢問題：給定不同面額的硬幣（coins），和一個總金額（amount）,寫一個函式來計算可以湊成總金額的硬幣組合數，假設每一種面額的硬幣有無數個，
說真的，我都快受不了了，是回溯不好用了嗎？
來我畫個圖：
比方說現在，有1、2、5三種面值的硬幣，總目標為10吧，
是吧，是回溯吧，這個我畫的決策樹可能是丑了點（我看得出來），將就著理解一下吧，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/263044.html
標籤：其他