01背包 P1507 NASA的食物计划

P1507 NASA的食物计划 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

普通01背包状态表示：f(i, j)表示前i件物品放入一个容量为j的背包可以获得的最大价值。

本题类似，f(i, j, k)表示前i件物品放入一个限制为j，且另一个限制为k的背包中可以获得的最大价值。可以进行就地滚动。

void solve() {
    int V,M; cin>>V>>M;
    int n; cin>>n;
    vector<array<int,3>> a(n); // V M Val
    for(auto &t: a) cin>>t[0]>>t[1]>>t[2];
    vector<vector<int>> f(V + 1, vector<int> (M + 1));
    for(int i = 0; i < n; ++i) {
        for(int j = V; j >= a[i][0]; --j) {
            for(int k = M; k >= a[i][1]; --k) {
                f[j][k] = max(f[j][k], f[j - a[i][0]][ k - a[i][1]] + a[i][2]);
            }
        } 
    }
    cout<<f[V][M];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15