動態規劃---01背包/完全背包

上個博客說道動態規劃的引入，今天看一下動態規劃的一個分支，01背包；

01背包問題

為什么，要叫他01背包呢，顧名思義，他的狀態只有0或者1兩種狀態；也就是，拿與不拿；
國際慣例，用一道題來說明；
洛谷P1048----采藥

現在他需要知道，到底采哪種藥，會使得價值最高；
假設，我們現在按照題目的樣例來想；

現在我們可用的時間是70；左邊這一串列示不同藥采的時間，上邊這一行表示背包大小；

首先第一行，由于71>70所以說，不管哪個狀態下，我們采藥的價值都是0；

接著看第二行，剛開始的時候，背包重量從1，開始加，所以，當背包大小小于69時，背包容量不夠，放不下藥，當背包大于等于69是，采藥所產生的價值為1；

再看下一行，當背包重量是1的時候，采藥可以產生的最大價值為2；之后一直向后遞推

這時，當背包大小為69的時候，我們有兩種選擇，一個是拿1不拿69，一個是拿69不拿1；顯然，拿1的價值更大；

當背包為70的時候，我們既可以拿1也可以拿69，此時最大價值就是3；

所以說，對于一件物品，我們可以選擇拿或者不拿，來確定其自身價值，我們用一個二維陣列dp來表示；
用w[i]表示每個物品重量，v[i]表示物品價值；

int dp[i][j] 表示對于第i個物品,背包大小為j的時候的最大價值；
此時對于i來說，如果此時背包大小夠裝下這個物品 (j>=w[i]) ，那么此時
dp[i]j[j]就是上一個物品時候 (dp[i-1][j]) 的狀態加上這個物品的價值v[i]，與此同時，背包的大小也要減小w[i] (dp[i-1][j-w[i]]) ；

即，dp[i][j]=max{dp[i-1][j-w[i]]+v[i]，dp[i-1][j]}

如果此時背包大小裝不下這個物品，那么dp[i][j]=dp[i-1][j];

主要的核心代碼就是：

for (int i = 1; i <= m; i++)
        for (int j = t; j >= 0; j--)
        {
            if (j >= w[i])
            {
                dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }

這個題的完整原始碼如下；

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[105][1005];
int w[105], v[105];
int main()
{
    int m,t;
    cin >> t >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> w[i]>> v[i];
    }
    for (int i = 1; i <= m; i++)
        for (int j = t; j >= 0; j--)
        {
            if (j >= w[i])
            {
                dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    cout << dp[m][t];
    return 0;
}

再看一道洛谷的01背包變形版；

這個題與上面不同的就是，他狀態有贏有輸，而贏和輸都會增加經驗值；
所以這個的狀態轉移方程就變成了；

dp[j]=max(dp[j-use[i]]+win[i],dp[j]+lose[i]);

完整代碼如下；

#include<bits/stdc++.h>
using namespace std;
long long use[1005],win[1005],lose[1005];
long long dp[1005];
int main()
{
	long long n,x;
	cin>>n>>x;
	for(int i=1;i<=n;i++)
	{
		cin>>lose[i]>>win[i]>>use[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=x;j>=0;j--)
		{
			if(j>=use[i])
			{
				dp[j]=max(dp[j-use[i]]+win[i],dp[j]+lose[i]);
			}
			else
			{
				dp[j]=dp[j]+lose[i];
			}
		}
	}
	cout<<dp[x]*5;
	return 0;
 } 

01背包的優化；

上面說到01背包需要一個二維陣列來記錄對應的狀態，但是二維陣列很容易就是出現MLE；

所以就有了，一維陣列的01背包；
從上面我們能看出dp[i]完全是由dp[i-1】遞推出來的；
所以我們只需要用一個dp[j]的一維陣列，通過每次更新最大價值來完成這個題；
具體代碼如下：

 for(int i=1;i<=m;i++) 
    {
        for(int j=t;j>=0;j--) 
        {
            if(j>=w[i])
            {
                dp[j]=max(dp[j-w[i]]+v[i], dp[j]);
            }
        }

這樣子大大減小了記憶體占用率；

完全背包

完全背包與01背包不同的是；01背包只有拿與不拿，而完全背包卻是可以一直拿，
所以，他的核心代碼相對于01背包就有了一點變換化

for(int i = 1;i <= m;i ++){
		for(int j = w[i];j <= T;j ++){
			f[j] = max(dp[j],dp[j - w[i]] + v[i]);
		}

例如下面這個題，就可以完全套用這個模板

#include<iostream>
#include<algorithm>
using namespace std;
const int maxm = 10010, maxt = 10000010;
long long v[maxm], t[maxm], f[maxt];
int main(){
	int T , m;
	cin >> T >> m;
	for(int i = 1;i <= m ;i ++) cin >> t[i] >> v[i];
	for(int i = 1;i <= m;i ++){
		for(int j = t[i];j <= T;j ++){
			f[j] = max(f[j],f[j - t[i]] + v[i]);
		}
	}
	cout << f[T];
}