01背包

Powered by:AB_IN 局外人

我太菜了，現在才學

看的入門班的錄播，大約明白了，

n n n是物品的個數， v v v是背包的容量， c [ i ] c[i] c[i]代表第 i i i物品的費用， w [ i ] w[i] w[i]代表第 i i i物品的價值，

先給出最原始推出來的式子

dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);

什么意思呢？

d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i件物品恰好放入一個容量為 j j j的背包里可以獲得的最大價值，

• d p [ i ? 1 ] [ j ] dp[i-1][j] dp[i?1][j]就表示，不選第 i i i個物品，就讓前 i ? 1 i-1 i?1個物品去組成容量為 j j j的背包，
• d p [ i ? 1 ] [ j ? c [ i ] ] dp[i-1][j-c[i]] dp[i?1][j?c[i]]就表示，選第 i i i個物品，讓 j ? c [ i ] j-c[i] j?c[i]的背包正好加上第 i i i個物品，容量不就正好為 j j j了嘛，
• 這兩個取最大值即可，

但問題是這樣太浪費空間了，可以通過式子看出 d p [ i ] [ ] dp[i][] dp[i][]只和 d p [ i ? 1 ] [ ] dp[i-1][] dp[i?1][]有關，也就是和上一行，再加上 i i i是從 1 1 1到 n n n的，也就是前面一些行就沒有用了，會很浪費空間，

所以便有了01滾動和就地滾動，

• 01滾動，顧名思義，就是兩行之間的相互利用， d p [ 0 / 1 ] [ j ] dp[0/1][j] dp[0/1][j]一行記錄前一行的值，另一行記錄當前行的值，

• 就地滾動，顧名思義，就是用一個一維陣列，之前的狀態和當前的狀態都在同一個陣列里，

  但如果 j j j從 c [ i ] c[i] c[i]到 v v v的話，會出現 b u g bug bug，一個物品會被算多次，因為 j j j會一直往右走到 v v v，比如一個放進去了， j j j往右走，會走到剛剛放進去的那個狀態，原先放進去的會被再放一遍，顯然這樣是錯的，因為上一行狀態和這一行狀態混了，

  那該怎么辦呢？

  讓 j j j從右往左走即可，上一行的狀態在 j j j的左邊，這一行的狀態在 j j j的右邊，

  代碼孕育而生，

	for(int i=1;i<=n;i++){
        for(int j=v;j>=c[i];j--){
            dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
        }
    }

愛玩游戲的Tom

#include<bits/stdc++.h>
using namespace std;
const int N=50005;
typedef long long ll;
ll n,m,dp[N],c[N],w[N];
int main()
{
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>c[i]>>w[i];
    }
    for(ll i=1;i<=n;i++){
        for(ll j=m;j>=c[i];j--){
            dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

完結，