嗨害嗨，作業來嘍
背包問題
01背包和完全背包問題都是一個背景下的：我有一個容量為M的背包，現在地上有N個物品，我跟個小偷似的眼里只有i個物品的價值vi和重量wi，現在我要做的就是為了偷的東西更值錢拿走一些東西，使它們的價值是所有方案里最大的
01背包
背景如上，01背包就是我眼前的這些東西都是孤品，只有一件，求最大價值，
那么有些人會先想到：我可不可以等他們輸入時先計算出他們的性價比，然后再去給他們的性價比排序，得出答案呢？這就是用貪心的思想去想這道問題了，但顯然不行，因為你無法把空間利用到最大，不用貪心，我們用什么？答案就是——動態規劃
我們可以把問題看成這樣：用一個二維陣列c[N][M]來表示N個物品放入M容量的背包中的最大價值，那么要計算最大價值，每個物品就只有兩種選擇方式
1.不拿，直接照抄c[i-1][j]
2.拿，拿的話我們首先要把j-w[i]把物品放進去，然后再把c[i][j-w[i]]中加上i物品的價值v[i]，即得：c[i][j-w[i]]+v[i]
也就是說，我們把每個物品都拆成這樣的選最優的問題，就可以得到一行很簡單的式子：max(c[i-1][j],c[i][j-w[i]]+v[i]);這就是狀態轉移方程式
那么有了這個我們就可以寫代碼了，但是注意初始化c[0][j]=0,c[i][0]=0:
1 for(int i=1;i<=n;i++){ 2 for(int j=1;j<=m;j++){ 3 if(j>=w[i]) c[i][j]=max(c[i-1][j],c[i][j-w[i]]+v[i]); 4 else c[i][j]=c[i-1][j]; 5 } 6 } 7 cout<<c[n][m];
注意，此時的空間復雜度為N*M
現在我們就要優化這個代碼
max(c[i-1][j],c[i][j-w[i]]+v[i]);
我們可以看到，這個式子里我們求第i個只需要知道i-1個物品的資料，那么就可以把二維陣列優化成一維陣列，但是因為每個物品只能取一次，為保留前面的資料，我們就只能從后面逆推
代碼：
1 for(int i=1;i<=n;i++) 2 for(int j=w[i];j<=m;j++) c[j]=max(c[j],c[j-w[i]]+v[i]); 3 cout<<c[m];
完全背包就是把逆推變成正推就歐啦
溜了溜了~
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/473392.html
標籤：C++