每种物品最多拿两个的背包问题

Tag: 笔试算法题 Posted on 2022-03-22 21:37:41 Edited on 2022-03-22 21:38:55 Views: 115

概述

n 种物品,有价值和重量,每种物品最多拿两个,给定重量求最大价值

动态规划

TLE,18%

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

vector<int> weights;
vector<int> powers;
vector<vector<int>> dp;

int helper(int i, int w) {
    if (i == weights.size() * 2) return 0;
    if (w == 0) return 0;
    if (dp[i][w] != -1) return dp[i][w];
    int realIdx = i / 2;
    int res = helper(i + 1, w);
    if (w >= weights[realIdx]) {
        res = max(res, powers[realIdx] + helper(i + 1, w - weights[realIdx]));
    }
    dp[i][w] == res;
    return res;
}

int main() {
    int n, w; cin >> n >> w;
    weights.resize(n);
    powers.resize(n);
    for (int i = 0; i < n; i ++) {
        cin >> weights[i] >> powers[i];
    }
    dp.resize(n * 2, vector<int>(w + 1, -1));
    cout << helper(0, w);
}

未经允许,禁止转载,本文源站链接:https://iamazing.cn/