少年Q

用户名：yin19990129

访问量：25369

签　名：

这次一定不水了！

等　　级
排　　名	181
经　　验	6821
参赛次数	2
文章发表	71
年　　龄	21
在职情况	学生
学　　校	宿迁学院
专　　业	软件工程

　　自我简介：

TA的其他文章

31.简化型背包-题解(C++代码)只做最好的思路！
浏览：402

32.极限跳跃-题解(C++代码)只做最好的思路！
浏览：138

33.同学的等待-题解(C++代码)只做最好的思路！
浏览：455

你可能喜欢

46.多重背包（C++代码）只做最好的思路！

　　作者: 少年Q　　　　发表时间：2020-04-14 22:52:12 浏览：781　|　评论：0　

原题链接：多重背包

这题是典型的0-1整型化背包问题，在dp问题中只能算是入门级别的题，dp主要是难在状态转移方程的设计和记忆化的搜索，学好动态规划（dp）还是需要一定数学基础和努力练习的。。。因为之前自己没怎么接触过dp，所以理解了大神网友的做法后，自己把这题码了一遍，还是比较简单的，这题可以说是dp问题的一个入门，代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
int w[100005],v[100005],dp[100005];
int main(){
	int n,m,pos=0;
	cin>>n>>m; 
	for(int i=1;i<=n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		for(int j=1;j<=c;j++){
			pos++;
			w[pos]=a;
			v[pos]=b;
		}
	}
	for(int i=1;i<=pos;i++){
		for(int j=m;j>=0;j--){
			if(j<w[i]){
				break;
			}
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<dp[m]<<endl;
	return 0;
}
```
*ps:动态规划其实也并不是那么玄乎，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤。
第一步骤：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？
第二步骤：找出数组元素之间的关系式，我觉得动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]…..dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。而这一步，也是最难的一步。
第三步骤：找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1]和dp[n-2]来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要通过关系式能够直接获得dp[2]和dp[1]的值，而这就是所谓的初始值。有了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 dp[n] 的值了，而 dp[n] 的含义是由你来定义的，你想求什么，就定义它是什么，这样，这道题也就解出来了。

0.0分

6 人评分

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

少年Q

TA的其他文章

你可能喜欢

关于逻辑非“！”与取反“~”运算符

用筛法求之N内的素数。（C语言代码）

【明明的随机数】（C语言代码）

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

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

46.多重背包（C++代码）只做最好的思路！

评论区

精彩推荐

C语言训练-计算1~N之间所有奇数之和（C语言代码）

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

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

C语言训练-列出最简真分数序列* （C语言代码）

简单的for循环

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

模拟计算器（C++代码）

2^k进制数（C语言描述，蓝桥杯）

格式化数据输出（C语言代码）

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

少年Q

TA的其他文章

你可能喜欢

关于逻辑非“！”与取反“~”运算符

用筛法求之N内的素数。 （C语言代码）

【明明的随机数】 （C语言代码）

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

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

46.多重背包 （C++代码）只做最好的思路！

评论区

精彩推荐

C语言训练-计算1~N之间所有奇数之和 （C语言代码）

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

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

C语言训练-列出最简真分数序列* （C语言代码）

简单的for循环

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

模拟计算器 （C++代码）

2^k进制数 （C语言描述，蓝桥杯）

格式化数据输出 （C语言代码）

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

用筛法求之N内的素数。（C语言代码）

【明明的随机数】（C语言代码）

46.多重背包（C++代码）只做最好的思路！

　　评论区

C语言训练-计算1~N之间所有奇数之和（C语言代码）

模拟计算器（C++代码）

2^k进制数（C语言描述，蓝桥杯）

格式化数据输出（C语言代码）