二维费用的背包问题

题目描述：

N件物品，容量是V的背包，背包能承受的最大重量是M

每件物品只能拿一次，体积是v[i]，重量是m[i]，价值是w[i]

问在容量和重量允许范围内，能获得的最大价值是多少

思路：

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, v;
int vv[MAX], mm[MAX];
int val[MAX];
int dp[105][105];

void work(){
    cin >> n >> v >> m;
    for(int i = 1; i <= n; ++i){
        cin >> vv[i] >> mm[i] >> val[i];
    }
    for(int i = 1; i <= n; ++i){
        for(int j = v; j >= vv[i]; --j){
            for(int k = m; k >= mm[i]; --k){
                dp[j][k] = max(dp[j][k], dp[j - vv[i]][k - mm[i]] + val[i]);
            }
        }
    }
    cout << dp[v][m] << endl;
}

int main(){
    io;
    work();
    return 0;
}

潜水员

题目描述：

潜水员需要携带若干个气缸，每个气缸中都有氧气和氮气，而不同深度的下潜需要不同数量的氧和氮，现在给你所需要的氧气和氮气的容量，问最小需要带的气缸的总重量是多少

思路：

上一个题是体积最多为j

这个题是体积最少为j

二者的状态转移方程不变，但是循环条件和初始条件需要改变

总结一下规律：

• 体积恰好为j，则初始dp[0]=0, dp[i]=inf, 循环条件v>=0
• 体积最多为j, 则初始化dp[i]=0, 循环条件v>=0
• 体积至少为j，则初始化dp[0] = 0,dp[i]=inf，v无限制，可以小于0，只需要和0取max就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int o2, n2, n;
int O2[MAX], N2[MAX];
int val[MAX];
int dp[30][100];
void work(){
    cin >> o2 >> n2 >> n;
    mem(dp, inf);
    dp[0][0] = 0;
    for(int i = 1; i <= n; ++i){
        cin >> O2[i] >> N2[i] >> val[i];
    }
    for(int i = 1; i <= n; ++i){
        for(int j = o2; j >= 0; --j){
            for(int k = n2; k >= 0; --k){
                dp[j][k] = min(dp[j][k], dp[max(0, j - O2[i])][max(0, k - N2[i])] + val[i]);
            }
        }
    }
    cout << dp[o2][n2] << endl;
}

int main(){
    io;
    work();
    return 0;
}