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

    
        标签：
        
            笔试算法题
        
    发布于：2022-03-22 21:37:41
    编辑于：2022-03-22 21:38:55
    浏览量：495

概述

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);
}

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