Jeopardize

用户名：uq_54581940915

访问量：1129

签　名：

好喜欢绫华啊，怎么办

等　　级
排　　名	1003
经　　验	3349
参赛次数	0
文章发表	35
年　　龄	0
在职情况	学生
学　　校	长江大学
专　　业

　　自我简介：

绫华绫华好喜欢你啊

TA的其他文章

蒟蒻勿怪，蒟蒻%%%%%%
浏览：76

你可能喜欢

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

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

A+B for Input-Output Practice (III) （C语言代码）

动态规划dp （蒟蒻）

　　作者: Jeopardize　　　　发表时间：2023-08-29 15:21:04 浏览：22　|　评论：0　

原题链接：蓝桥杯算法提高VIP-01背包

```cpp
/*
	对于一个物品
	1.如果体积大于背包的容积 
		则该物品不能放入背包 
		即前i个物品在容积为j的价值等于前i-1个物品在容积为j的价值
		所以dp[i][j] = dp[i-1][j]  
	2.如果体积小于背包容积
		则物品可以放入背包，对于这个物品，又有两种选择 一种是放 一种是不放
		不放 dp[i][j] = dp[i-1][j] 
		放 dp[i][j] = dp[i-1][j-w[i]]+v[i]
		题目要求的是求最大值 
		所以dp[i][j] = max(dp[i-1][j] , dp[i-1][j-w[i]]+v[i])
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3+10;
int dp[210][maxn]; 
//dp[i][j]表示前i个物品在容积为j的背包中的最大价值

int v[210] , w[210]; //v[i] 第i个物品的价值，w[i] 第i个物品的体积
int n , m;
int main()
{
	//输入
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; i++) scanf("%d%d",&w[i],&v[i]);
	
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 1 ; j <= m ; j ++)
		{
			if(w[i] > j) dp[i][j] = dp[i-1][j];
			else dp[i][j] = max(dp[i-1][j] , dp[i-1][j-w[i]] + v[i]);
		}
	cout<<dp[n][m];
	return 0;
}	
```
似乎好像还可以运用记忆化来优化算法（错了请指出）
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3+10;
int dp[210][maxn];
int v[210] , w[210];
int n , m;
int solve(int i , int j)
{
	if(dp[i][j] != 0) return dp[i][j];
	if(i == 0) return 0;
	int res;
	if(w[i] > j) return solve(i-1,j);
	else res = max(solve(i-1,j) , solve(i-1,j-w[i]) + v[i]);
	return dp[i][j] = res;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n ; i ++)	scanf("%d%d",&w[i],&v[i]);
	
	cout<<solve(n,m);
	return 0;
}
```

0.0分

0 人评分

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

Jeopardize

TA的其他文章

你可能喜欢

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

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

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

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

A+B for Input-Output Practice (III) （C语言代码）

动态规划dp （蒟蒻）

评论区

精彩推荐

C语言考试练习题_一元二次方程（C语言代码）

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

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

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

IP判断（C语言代码）

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

时间转换（C语言代码）

1052题解（链表操作）

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

【计算球体积】（C语言代码）

Jeopardize

TA的其他文章

你可能喜欢

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

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

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

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

A+B for Input-Output Practice (III) （C语言代码）

动态规划dp （蒟蒻）

评论区

精彩推荐

C语言考试练习题_一元二次方程 （C语言代码）

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

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

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

IP判断 （C语言代码）

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

时间转换 （C语言代码）

1052题解（链表操作）

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

【计算球体积】 （C语言代码）

　　评论区

C语言考试练习题_一元二次方程（C语言代码）

IP判断（C语言代码）

时间转换（C语言代码）

【计算球体积】（C语言代码）