算法至美

用户名：uq_54514514336

访问量：7728

签　名：

等　　级
排　　名	1364
经　　验	2945
参赛次数	0
文章发表	43
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1538-清点人数-题解（各语言代码）
浏览：331

信息学奥赛一本通T1308-高精除-题解
浏览：154

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

信息学奥赛一本通T1272-分组背包-题解（各语言代码）

　　作者: 算法至美　　　　发表时间：2022-07-08 09:21:53 浏览：171　|　评论：0　

原题链接：信息学奥赛一本通T1272-分组背包

**python**
```python
v,n,t=map(int,input().split())
l=[[] for _ in range(-~t)]
dp=[0]*-~v
for _ in range(n):
	w,c,p=map(int,input().split())
	l[p].append((w,c))
for i in l:
	i.sort()
	for j in range(v,0,~0):
		for w,c in i:
			if w>j:break
			elif dp[j]<dp[j-w]+c:
				dp[j]=dp[j-w]+c
print(dp[v])
```
**C++**
```cpp
#include<map>
#include<vector>
#include<iostream>
using namespace std;
int main(){
	int v,n,t;
	cin>>v>>n>>t;
	int*dp=new int[-~v]();
	vector<multimap<int,int> >l(-~t);
	for(int w,c,p;n--;l[p].insert(make_pair(w,c)))
		cin>>w>>c>>p;
	for(const auto&i:l)
		for(int j=v;j;--j)
			for(const auto&k:i)
				if(k.first<=j)
					dp[j]=max(dp[j],dp[j-k.first]+k.second);
				else break;
	cout<<dp[v];
	delete[]dp;
}
```
**java**
```java
import java.util.Scanner;
import java.util.Map.Entry;
import java.util.ArrayList;
import java.util.stream.IntStream;
public class Main {
	public static void main(String[] args) {
		final Scanner in = new Scanner(System.in);
		final int v = in.nextInt(), n = in.nextInt(), t = in.nextInt();
		final ArrayList<ArrayList<Entry<Integer, Integer>>> l = IntStream.rangeClosed(0, t).mapToObj(i -> new ArrayList<Entry<Integer, Integer>>()).collect(java.util.stream.Collectors.toCollection(ArrayList::new));
		final int[] dp = new int[-~v];
		IntStream.range(0, n).forEach(i -> {
			final Entry<Integer, Integer> e = new java.util.AbstractMap.SimpleEntry<>(in.nextInt(), in.nextInt());
			l.get(in.nextInt()).add(e);
		});
		in.close();
		for (ArrayList<Entry<Integer, Integer>> i : l) {
			i.sort(Entry.comparingByKey());
			for (int j = v; j != 0; --j)
				for (Entry<Integer, Integer> k : i)
					if (k.getKey() > j)
						break;
					else if (dp[j] < dp[j - k.getKey()] + k.getValue())
						dp[j] = dp[j - k.getKey()] + k.getValue();
		}
		System.out.print(dp[v]);
	}
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

算法至美

TA的其他文章

你可能喜欢

逆反的01串（C++代码）（依旧推荐switch）

点我有惊喜！你懂得！

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

信息学奥赛一本通T1272-分组背包-题解（各语言代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

DNA （C语言描述，数据结构）

求圆的面积（C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

筛排处理（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.3 （C++代码）

简单的a+b （C语言代码）

Manchester- Hello, world!

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

算法至美

TA的其他文章

你可能喜欢

逆反的01串 （C++代码）（依旧推荐switch）

点我有惊喜！你懂得！

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

信息学奥赛一本通T1272-分组背包-题解（各语言代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

DNA （C语言描述，数据结构）

求圆的面积 （C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

筛排处理 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.3 （C++代码）

简单的a+b （C语言代码）

Manchester- Hello, world!

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

逆反的01串（C++代码）（依旧推荐switch）

　　评论区

求圆的面积（C语言代码）

筛排处理（C语言代码）