先解決第?問

1. 狀態表?：
   dp[i][j]表?：從前i個物品中挑選，總體積不超過j，所有的選法中，能挑選出來的最?價
   值。（這?是和01背包?樣噠）
   那我們的最終結果就是dp[n][V] 。
2. 狀態轉移?程：
   線性dp狀態轉移?程分析?式，?般都是根據最后?步的狀況，來分情況討論。但是最后?個物品能選很多個，因此我們的需要分很多情況：
   a. 選0個第i個物品：此時相當于就是去前i-1個物品中挑選，總體積不超過j。此時最?價值為dp[i - 1][j]；
   b. 選1個第i個物品：此時相當于就是去前i-1個物品中挑選，總體積不超過j-v[i]。因為挑選了?個i物品，此時最?價值為dp[i-1][j-v[i]]+w[i]；
   c. 選2個第i個物品：此時相當于就是去前o-1個物品中挑選，總體積不超過j-2 x v[i]。因為挑選了兩個i物品，此時最?價值為dp[i-1][j - 2 v[i]] + 2 * w[i]；
   綜上，狀態轉移?程為：
   dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i], dp[i - 1][j - 2 × v[i]] + 2 × w[i]...
   當計算?個狀態的時候，需要?個循環才能搞定的時候，就要想到去優化。優化的?向就是??個或者兩個狀態來表?這?堆的狀態，通常就是?數學的?式做?下等價替換。
   觀察發現第?維是有規律的變化的，因此去看看dp[i][j - v[i]]這個狀態：
   dp[i][j - v[i]] = max(dp[i - 1][j - v[i]], dp[i - 1][j - 2 × v[i]] + w[i], dp[i - 1][j - 3 × v[i]] + 2 × w[i]...)
   我們發現，把dp[i][j - v[i]]加上w[i]正好和dp[i][j]中除了第?項以外的全部?致，因們可以修改狀態轉移?程為：
   dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
3. 初始化：
   我們多加??，?便我們的初始化，此時僅需將第??初始化為0即可。因為什么也不選，也能滿?體積不?于j的情況，此時的價值為0。
4. 填表順序：
   根據狀態轉移?程，我們僅需從上往下填表即可。

接下來解決第?問：
第?問僅需修改?下初始化以及最終結果即可。

1. 初始化：
   因為有可能湊不?j體積的物品，因此我們把不合法的狀態設置為負?窮。這樣在取最?值的時候，就不會考慮到這個位置的值。負?窮?般設置為-0x3f3f3f3f即可。
   然后把dp[0][0]修改成0，因為這是?個合法的狀態，最?價值是0，也讓后續填表是正確
   的。
2. 返回值：
   在最后拿結果的時候，也要判斷?下最后?個位置是不是?于0 ，因為有可能湊不?
   不能判斷是否等于-0x3f3f3f3f，因為這個位置的值會被更新，只不過之前的值太?，導致更新后還是?于0的。

#include <bits/stdc++.h>
using namespace std;const int N = 1010;int n, m;
int v[N], w[N];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];//第一問for (int i = 1; i <= n; i++){for (int j = 0; j <= m; j++){f[i][j] = f[i-1][j];if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]);}}cout << f[n][m] << endl;//第二問memset(f, -0x3f, sizeof f);f[0][0] = 0;for (int i = 1; i <= n; i++){for (int j = 0; j <= m; j++){f[i][j] = f[i-1][j];if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]);}}if (f[n][m] < 0) cout << 0 << endl;else cout << f[n][m] << endl;return 0;
}

空間優化

#include <bits/stdc++.h>
using namespace std;const int N = 1010;int n, m;
int v[N], w[N];
int f[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];//第一問for (int i = 1; i <= n; i++){for (int j = v[i]; j <= m; j++){f[j] = max(f[j], f[j-v[i]] + w[i]);}}cout << f[m] << endl;//第二問memset(f, -0x3f, sizeof f);f[0] = 0;for (int i = 1; i <= n; i++){for (int j = v[i]; j <= m; j++){f[j] = max(f[j], f[j-v[i]] + w[i]);}}if (f[m] < 0) cout << 0 << endl;else cout << f[m] << endl;return 0;
}

完全背包模版題。

1. 狀態表?：
   dp[i][j] 表?：從前i 個藥材中挑選，總時間不超過j ，此時能采摘到的最?價值。
   那么dp[n][m]就是結果。
2. 狀態轉移?程：
   對于i 位置的藥材，可以選擇采0, 1, 2, 3… 個：
   a. 選0 個：最?價值為dp[i - 1][j] ；
   b. 選1 個：最?價值為dp[i - 1][j - t[i]] + v[i] ；
   c. 選2 個：最?價值為dp[i - 1][j - 2 × t[i]] + 2 × v[i] ；
   d. …
   由于要的是最?價值，應該是上述所有情況的最?值。其中第?個往后的狀態可以?dp[i][j - t[i]] + v[i]替代，因此狀態轉移?程為
   dp[i][j] = max(dp[i - 1][j], dp[i][j - t[i]] + v[i])
3. 初始化：
   全部初始化0 ，不影響后續填表的正確性。
4. 填表順序：
   從上往下每??，每??從左往右。
   空間優化版本也是如此

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 1e4 + 10, M = 1e7 + 10;int n, m;
int t[N], w[N];
LL f[M];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> m >> n;for (int i = 1; i <= n; i++) cin >> t[i] >> w[i];for (int i = 1; i <= n; i++){for (int j = t[i]; j <= m; j++){f[j] = max(f[j], f[j-t[i]]+w[i]);       }}cout << f[m] << endl;return 0;
}

完全背包簡單變形。

1. 狀態表?：
   dp[i][j]表?：從前i 個?草公司中挑選，總重量?少為j 磅，此時的最?開銷。
   注意注意注意！這是我們遇到的第三類限制情況。
   之前的限制條件為不超過j ，或者是恰好等于j 。這道題的限定條件是?少為j ，也就是說可以超過j。這會對我們分析狀態轉移?程的時候造成影響。
   根據狀態表?，dp[n][m] 就是結果。
2. 狀態轉移?程：
   對于i 位置的公司，可以選擇買0, 1, 2, 3… 個：
   a. 選0 個：開銷為dp[i - 1][j] ；
   b. 選1個：開銷為dp[i - 1][j - p[i]]+c[i] 。問題來了，狀態表???是?少為j ，也就是說j - p[i]?于0也是合法的。因為公司提供了p[i]的重量，?于j，是符合要求的。但是dp表的下標不能是負數，處理這種情況的?式就是對j-p[i]與0取?個最?值。當重量很?的時，只?去前?湊重量為0的就?夠了，這樣就符合我們的狀態表?了。因此，最終開銷為
   dp[i - 1][max(0, j - p[i])] + c[i]
   c. 選2 個：開銷為dp[i - 1][max(0, j - 2 × p[i])] + 2 × c[i] ；
   d. …
   由于要的是最?開銷，應該是上述所有情況的最?值。
   其中第?個往后的狀態可以?dp[i][max(0, j - p[i])] + c[i] 替代，因此狀態轉移?程為dp[i][j] = min(dp[i - 1][j], dp[i][max(0, j - p[i])] + c[i])
3. 初始化：
   全部初始化正?窮?0x3f3f3f3f ，然后dp[0][0] = 0 ，不影響后續填表的正確性。
4. 填表順序：
   從上往下每??，每??從左往右。
   空間優化版本也是如此

#include <bits/stdc++.h>
using namespace std;const int N = 110, M = 50010;int n, m;
int p[N], c[N];
int f[N][M];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> p[i] >> c[i];memset(f, 0x3f, sizeof f);f[0][0] = 0;for (int i = 1; i <= n; i++){for (int j = 0; j <= m; j++){f[i][j] = min(f[i-1][j], f[i][max(0, j-p[i])] + c[i]);        }}cout << f[n][m] << endl;return 0;
}

空間優化

#include <bits/stdc++.h>
using namespace std;const int N = 110, M = 50010;int n, m;
int p[N], c[N];
int f[M];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> p[i] >> c[i];memset(f, 0x3f, sizeof f);f[0] = 0;for (int i = 1; i <= n; i++){for (int j = 0; j <= m; j++){f[j] = min(f[j], f[max(0, j-p[i])] + c[i]);        }}cout << f[m] << endl;return 0;
}

總策略：貪?。從前往后，?天?天的考慮如何最??幣。
因為紀念品可以在當天買，當天賣。因此所有的交易情況，就可以轉換成"某天買隔天賣"的情況。那么，我們就可以貪?的將每?天能拿到的最?利潤全都拿到?：

• 從第?天開始，把第?天的?幣看成限制條件，第?天的?幣看成價值，求出：在不超過m的情況下，能獲得的最?價值m1；
• 然后時間來到第?天，把這?天的?幣看成限制條件，第三天的?幣看成價值，求出：在不超m1的情況下，能獲得的最?價值m2；
• 以此類推，直到把第t - 1天的情況計算出來，能獲得最?價值就是結果。
  接下來就處理，拿到第i?以及i+1?數據，在最??幣數量為m的前提下，獲得的最?利潤是
  多少？
• 因為每?個紀念品都可以?限次購買；
• 把前??看成限制，后??減去前??的值看成價值，就變成了標準的完全背包問題。
  那我們的解決?法就是????的跑完全背包，跑??拿到最?價值，然后放到下??繼續跑，直到跑完倒數第??。
  完全背包的邏輯：

1. 狀態表?：
   dp[i][j]表?從前i 個紀念品中挑選，總花費不超過j 的情況下，最?的利潤。
   那么，dp[n][m] + m就是能得到的最??幣數量
2. 狀態轉移?程：
   根據最后?個紀念品選的數量，分成如下情況：
   a. 如果選0 個：能獲得的最??幣數量為dp[i - 1][j] ；
   b. 如果選1 個：能獲得的最??幣數量為dp[i - 1][j - w[i]] + v[i] - w[i] ；
   c. 如果選2 個：能獲得的最??幣數量為dp[i - 1][j - 2 × w[i]] + 2 × (v[i] - w[i])
   d. …
   其中除了第?個狀態外的所有狀態都可以?dp[i][j - w[i]] + v[i] - w[i] 來表?，?因為要的是最?值，所以狀態轉移?程就是所有情況的最?值。
3. 初始化
   全為0 即可

#include <bits/stdc++.h>
using namespace std;const int N = 110, M = 1e4 + 10;int t, n, m;
int p[N][N];
int f[M];//完全背包
int solve(int v[], int w[], int m)
{//清空數據memset(f, 0, sizeof f);for (int i = 1; i <= n; i++){for (int j = v[i]; j <= m; j++){f[j] = max(f[j], f[j-v[i]] + w[i] - v[i]);        }}return f[m] + m;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> t >> n >> m;for (int i = 1; i <= t; i++)for (int j = 1; j <= n; j++)cin >> p[i][j];//貪心for (int i = 1; i < t; i++){m = solve(p[i], p[i+1], m);       }cout << m << endl;return 0;
}