从栈中取出K个硬币的最大面值和-分组背包

2218. 从栈中取出 K 个硬币的最大面值和 - 力扣（LeetCode）

Solution

比较神奇的思路，注意到每次只能从栈中取出前i个元素，每个单独数字的重量为1，于是就可以转化为一个经典的分组背包问题。

这里的一个代价定义也比较重要，由于只能取k次，相当于背包容量是k，每个数字的重量为1。

#include<iostream>
#include<vector>
using namespace std;class Solution {
public://每个栈都可以选前1，2，3...n个数的和，每个数的价值为本身的数值，代价为1//于是每个栈进行前缀和处理之后都可以看作一个组，从这个组中选择一个物品//转换为分组背包问题int maxValueOfCoins(vector<vector<int>>& piles, int k) {int n = piles.size();vector<vector<int>>w(n + 1);vector<vector<int>>v(n + 1);for (int i = 0; i < n; ++i) {int s = 0;for (int j = 0; j < piles[i].size(); ++j) {s += piles[i][j];v[i].push_back(s);w[i].push_back(j + 1);}}vector<int>dp(k + 1, 0);for (int i = 0; i < n; ++i) {for (int j = k; j >= 0; --j) {for (int x = 0; x < w[i].size(); ++x) {if (j >= w[i][x]) dp[j] = max(dp[j], dp[j - w[i][x]] + v[i][x]);}}}return dp[k];}
};int main() {return 0;
}