Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 4d38172

Browse files
committed
feat: add solutions to lc problem: No.2218
No.2218.Maximum Value of K Coins From Piles
1 parent 9496493 commit 4d38172

File tree

9 files changed

+325
-2
lines changed

9 files changed

+325
-2
lines changed

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -120,6 +120,7 @@
120120
- [最后一块石头的重量 II](/solution/1000-1099/1049.Last%20Stone%20Weight%20II/README.md) - `0-1 背包问题`
121121
- [零钱兑换](/solution/0300-0399/0322.Coin%20Change/README.md) - `完全背包问题`
122122
- [组合总和 IV](/solution/0300-0399/0377.Combination%20Sum%20IV/README.md) - `完全背包问题`
123+
- [从栈中取出 K 个硬币的最大面值和](/solution/2200-2299/2218.Maximum%20Value%20of%20K%20Coins%20From%20Piles/README.md) - `分组背包问题`
123124
<!-- 背包问题、状态机模型、状压DP、区间DP、树形DP、数位DP 待补充 -->
124125

125126
### 5. 高级数据结构

‎README_EN.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -116,6 +116,7 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
116116
- [Last Stone Weight II](/solution/1000-1099/1049.Last%20Stone%20Weight%20II/README_EN.md) - `0-1 Knapsack problem`
117117
- [Coin Change](/solution/0300-0399/0322.Coin%20Change/README_EN.md) - `Unbounded Knapsack problem`
118118
- [Combination Sum IV](/solution/0300-0399/0377.Combination%20Sum%20IV/README_EN.md) - `Unbounded Knapsack problem`
119+
- [Maximum Value of K Coins From Piles](/solution/2200-2299/2218.Maximum%20Value%20of%20K%20Coins%20From%20Piles/README_EN.md) - `Group Knapsack problem`
119120

120121
### 5. Advanced Data Structures
121122

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,14 @@
11
class Solution:
22
def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:
33
l = (intLength + 1) >> 1
4-
start, end = 10**(l - 1), 10**l - 1
4+
start, end = 10**(l - 1), 10**l - 1
55
ans = []
66
for q in queries:
77
v = start + q - 1
88
if v > end:
99
ans.append(-1)
1010
continue
1111
s = str(v)
12-
s += s[::-1][intLength % 2:]
12+
s += s[::-1][intLength % 2:]
1313
ans.append(int(s))
1414
return ans

‎solution/2200-2299/2218.Maximum Value of K Coins From Piles/README.md‎

Lines changed: 121 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -50,22 +50,143 @@
5050

5151
<!-- 这里可写通用的实现逻辑 -->
5252

53+
**方法一:动态规划**
54+
55+
对每个栈求前缀和 $s,ドル$s_i$ 视为一个体积为 $i$ 且价值为 $s_i$ 的物品。
56+
57+
问题转化为求从 $n$ 个物品组中取物品体积为 $k,ドル且每组最多取一个物品时的最大价值和。
58+
59+
定义 $dp[i][j]$ 表示从前 $i$ 个组中取体积之和为 $j$ 的物品时的最大价值和。
60+
61+
枚举第 $i$ 组所有物品,设当前物品体积为 $w,ドル价值为 $v,ドル则有 $f[i][j]=max(f[i][j],f[i-1][j-w]+v)$。
62+
5363
<!-- tabs:start -->
5464

5565
### **Python3**
5666

5767
<!-- 这里可写当前语言的特殊实现逻辑 -->
5868

5969
```python
70+
class Solution:
71+
def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
72+
presum = [list(accumulate(p, initial=0)) for p in piles]
73+
n = len(piles)
74+
dp = [[0] * (k + 1) for _ in range(n + 1)]
75+
for i, s in enumerate(presum, 1):
76+
for j in range(k + 1):
77+
for idx, v in enumerate(s):
78+
if j >= idx:
79+
dp[i][j] = max(dp[i][j], dp[i - 1][j - idx] + v)
80+
return dp[-1][-1]
81+
```
6082

83+
```python
84+
class Solution:
85+
def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
86+
presum = [list(accumulate(p, initial=0)) for p in piles]
87+
dp = [0] * (k + 1)
88+
for s in presum:
89+
for j in range(k, -1, -1):
90+
for idx, v in enumerate(s):
91+
if j >= idx:
92+
dp[j] = max(dp[j], dp[j - idx] + v)
93+
return dp[-1]
6194
```
6295

6396
### **Java**
6497

6598
<!-- 这里可写当前语言的特殊实现逻辑 -->
6699

67100
```java
101+
class Solution {
102+
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
103+
int n = piles.size();
104+
List<int[]> presum = new ArrayList<>();
105+
for (List<Integer> p : piles) {
106+
int m = p.size();
107+
int[] s = new int[m + 1];
108+
for (int i = 0; i < m; ++i) {
109+
s[i + 1] = s[i] + p.get(i);
110+
}
111+
presum.add(s);
112+
}
113+
int[] dp = new int[k + 1];
114+
for (int[] s : presum) {
115+
for (int j = k; j >= 0; --j) {
116+
for (int idx = 0; idx < s.length; ++idx) {
117+
if (j >= idx) {
118+
dp[j] = Math.max(dp[j], dp[j - idx] + s[idx]);
119+
}
120+
}
121+
}
122+
}
123+
return dp[k];
124+
}
125+
}
126+
```
127+
128+
### **C++**
129+
130+
```cpp
131+
class Solution {
132+
public:
133+
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
134+
vector<vector<int>> presum;
135+
for (auto& p : piles)
136+
{
137+
int m = p.size();
138+
vector<int> s(m + 1);
139+
for (int i = 0; i < m; ++i) s[i + 1] = s[i] + p[i];
140+
presum.push_back(s);
141+
}
142+
vector<int> dp(k + 1);
143+
for (auto& s : presum)
144+
{
145+
for (int j = k; ~j; --j)
146+
{
147+
for (int idx = 0; idx < s.size(); ++idx)
148+
{
149+
if (j >= idx) dp[j] = max(dp[j], dp[j - idx] + s[idx]);
150+
}
151+
}
152+
}
153+
return dp[k];
154+
}
155+
};
156+
```
68157
158+
### **Go**
159+
160+
```go
161+
func maxValueOfCoins(piles [][]int, k int) int {
162+
var presum [][]int
163+
for _, p := range piles {
164+
m := len(p)
165+
s := make([]int, m+1)
166+
for i, v := range p {
167+
s[i+1] = s[i] + v
168+
}
169+
presum = append(presum, s)
170+
}
171+
dp := make([]int, k+1)
172+
for _, s := range presum {
173+
for j := k; j >= 0; j-- {
174+
for idx, v := range s {
175+
if j >= idx {
176+
dp[j] = max(dp[j], dp[j-idx]+v)
177+
}
178+
}
179+
}
180+
}
181+
return dp[k]
182+
}
183+
184+
func max(a, b int) int {
185+
if a > b {
186+
return a
187+
}
188+
return b
189+
}
69190
```
70191

71192
### **TypeScript**

‎solution/2200-2299/2218.Maximum Value of K Coins From Piles/README_EN.md‎

Lines changed: 111 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -47,13 +47,124 @@ The maximum total we can obtain is 101.
4747
### **Python3**
4848

4949
```python
50+
class Solution:
51+
def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
52+
presum = [list(accumulate(p, initial=0)) for p in piles]
53+
n = len(piles)
54+
dp = [[0] * (k + 1) for _ in range(n + 1)]
55+
for i, s in enumerate(presum, 1):
56+
for j in range(k + 1):
57+
for idx, v in enumerate(s):
58+
if j >= idx:
59+
dp[i][j] = max(dp[i][j], dp[i - 1][j - idx] + v)
60+
return dp[-1][-1]
61+
```
5062

63+
```python
64+
class Solution:
65+
def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
66+
presum = [list(accumulate(p, initial=0)) for p in piles]
67+
dp = [0] * (k + 1)
68+
for s in presum:
69+
for j in range(k, -1, -1):
70+
for idx, v in enumerate(s):
71+
if j >= idx:
72+
dp[j] = max(dp[j], dp[j - idx] + v)
73+
return dp[-1]
5174
```
5275

5376
### **Java**
5477

5578
```java
79+
class Solution {
80+
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
81+
int n = piles.size();
82+
List<int[]> presum = new ArrayList<>();
83+
for (List<Integer> p : piles) {
84+
int m = p.size();
85+
int[] s = new int[m + 1];
86+
for (int i = 0; i < m; ++i) {
87+
s[i + 1] = s[i] + p.get(i);
88+
}
89+
presum.add(s);
90+
}
91+
int[] dp = new int[k + 1];
92+
for (int[] s : presum) {
93+
for (int j = k; j >= 0; --j) {
94+
for (int idx = 0; idx < s.length; ++idx) {
95+
if (j >= idx) {
96+
dp[j] = Math.max(dp[j], dp[j - idx] + s[idx]);
97+
}
98+
}
99+
}
100+
}
101+
return dp[k];
102+
}
103+
}
104+
```
105+
106+
### **C++**
107+
108+
```cpp
109+
class Solution {
110+
public:
111+
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
112+
vector<vector<int>> presum;
113+
for (auto& p : piles)
114+
{
115+
int m = p.size();
116+
vector<int> s(m + 1);
117+
for (int i = 0; i < m; ++i) s[i + 1] = s[i] + p[i];
118+
presum.push_back(s);
119+
}
120+
vector<int> dp(k + 1);
121+
for (auto& s : presum)
122+
{
123+
for (int j = k; ~j; --j)
124+
{
125+
for (int idx = 0; idx < s.size(); ++idx)
126+
{
127+
if (j >= idx) dp[j] = max(dp[j], dp[j - idx] + s[idx]);
128+
}
129+
}
130+
}
131+
return dp[k];
132+
}
133+
};
134+
```
56135
136+
### **Go**
137+
138+
```go
139+
func maxValueOfCoins(piles [][]int, k int) int {
140+
var presum [][]int
141+
for _, p := range piles {
142+
m := len(p)
143+
s := make([]int, m+1)
144+
for i, v := range p {
145+
s[i+1] = s[i] + v
146+
}
147+
presum = append(presum, s)
148+
}
149+
dp := make([]int, k+1)
150+
for _, s := range presum {
151+
for j := k; j >= 0; j-- {
152+
for idx, v := range s {
153+
if j >= idx {
154+
dp[j] = max(dp[j], dp[j-idx]+v)
155+
}
156+
}
157+
}
158+
}
159+
return dp[k]
160+
}
161+
162+
func max(a, b int) int {
163+
if a > b {
164+
return a
165+
}
166+
return b
167+
}
57168
```
58169

59170
### **TypeScript**
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
class Solution {
2+
public:
3+
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
4+
vector<vector<int>> presum;
5+
for (auto& p : piles)
6+
{
7+
int m = p.size();
8+
vector<int> s(m + 1);
9+
for (int i = 0; i < m; ++i) s[i + 1] = s[i] + p[i];
10+
presum.push_back(s);
11+
}
12+
vector<int> dp(k + 1);
13+
for (auto& s : presum)
14+
{
15+
for (int j = k; ~j; --j)
16+
{
17+
for (int idx = 0; idx < s.size(); ++idx)
18+
{
19+
if (j >= idx) dp[j] = max(dp[j], dp[j - idx] + s[idx]);
20+
}
21+
}
22+
}
23+
return dp[k];
24+
}
25+
};
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
func maxValueOfCoins(piles [][]int, k int) int {
2+
var presum [][]int
3+
for _, p := range piles {
4+
m := len(p)
5+
s := make([]int, m+1)
6+
for i, v := range p {
7+
s[i+1] = s[i] + v
8+
}
9+
presum = append(presum, s)
10+
}
11+
dp := make([]int, k+1)
12+
for _, s := range presum {
13+
for j := k; j >= 0; j-- {
14+
for idx, v := range s {
15+
if j >= idx {
16+
dp[j] = max(dp[j], dp[j-idx]+v)
17+
}
18+
}
19+
}
20+
}
21+
return dp[k]
22+
}
23+
24+
func max(a, b int) int {
25+
if a > b {
26+
return a
27+
}
28+
return b
29+
}
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
class Solution {
2+
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
3+
int n = piles.size();
4+
List<int[]> presum = new ArrayList<>();
5+
for (List<Integer> p : piles) {
6+
int m = p.size();
7+
int[] s = new int[m + 1];
8+
for (int i = 0; i < m; ++i) {
9+
s[i + 1] = s[i] + p.get(i);
10+
}
11+
presum.add(s);
12+
}
13+
int[] dp = new int[k + 1];
14+
for (int[] s : presum) {
15+
for (int j = k; j >= 0; --j) {
16+
for (int idx = 0; idx < s.length; ++idx) {
17+
if (j >= idx) {
18+
dp[j] = Math.max(dp[j], dp[j - idx] + s[idx]);
19+
}
20+
}
21+
}
22+
}
23+
return dp[k];
24+
}
25+
}
Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
class Solution:
2+
def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
3+
presum = [list(accumulate(p, initial=0)) for p in piles]
4+
dp = [0] * (k + 1)
5+
for s in presum:
6+
for j in range(k, -1, -1):
7+
for idx, v in enumerate(s):
8+
if j >= idx:
9+
dp[j] = max(dp[j], dp[j - idx] + v)
10+
return dp[-1]

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /