dp背包

#include<bits/stdc++.h> using namespace std; int p[10005]; int w[1005]; int dp[10005][3005]; int main(){ int m,n; cin>>m>>n; for(int i = 1;i<=n;i++){ cin>>w[i]; cin>>p[i]; } for(int i = 1;i<=n;i++){ for(int j = 1;j<=m;j++){ if(w[i]<=j) dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]); else dp[i][j] = dp[i-1][j]; } } cout<<dp[n][m]; return 0; }

模板题，没什么好说的

(这篇题解可能和别的题解不同,一共有两个完整的AC代码) 解题思路 很典型的01背包问题 可以选择二维dp或者一维dp 二维DP思路: 1. 遍历每一个状态 2. 根据前一个状态，选择装或者不装之间的较大值 3. 取最末状态，最大容量为答案 AC代码 二维DP代码 > 执行用时 8ms > 内存消耗 0.97MB 一维DP代码 > 执行用时 5ms > 内存消耗 0.59MB 欢迎加入团队 制作题解不易,跪求点赞!!!

点赞

dp模板啊

深度优先搜索

#include<bits/stdc++.h> using namespace std; int t,m; int c[105]; int v[105]; int dp[105][1005]; int main(){ cin>>t>>m; for(int i=1;i<=m;i++) { cin>>c[i]>>v[i]; } for(int i=1;i<=m;i++) { for(int j=1;j<=t;j++) { dp[i][j] = dp[i-1][j]; if(j>=c[i]) dp[i][j] = max(dp[i-1][j] , dp[i-1][j-c[i]]+v[i]); } } cout<<dp[m][t]; return 0; }

#include <bits/stdc++.h> using namespace std; int dp[101][1010],b[110],f[110]; int a,m; int main(){ }

本蒟蒻第n次写题解 一维dp： 二维的： 其实题目很简单，像我一样的蒟蒻都能做

01背包问题 常见类型 这种问题主要内容大概是： 一个有n容量的背包，和一些有一定质量和价值的物品，要求在背包不超过装填范围的情况下带走价值最高的物品 聪明的同学已经开始说话了那么为什么不用贪心呢？因为贪心只能保证一个物品拿到最优解，不能保证全部是最优解。举个例子： 我有一个背包，有10的容量，一共有4件物品 w1 = 8, v1 = 9 w2 = 3, v2 = 3 w3 = 4, v3 = 4 w4 = 3, v4 = 3 如果用贪心算法，那么会默认放入“性价比”最高的w1，但是，放入w1后无法放入其他物品，但事实上我们发现如果装入w2,w3,w4，背包并没有溢出，而且总价值为10，明显大于只放入w1的情况。 所以我们需要用一种新的算法，让他可以考虑到所有的情况，那么我们就引入动态规划 本题代码 话不多说了，代码里啥都有： 怎么样是不是很简单 01背包就是这样的，同时也是最经典的动态规划问题 同时有野心的同学们可以看一下这个网站（CSDN的内容），学习一下其他的背包问题 ok就到这了

old big 来拯救你们了 #include<bits/stdc++.h> using namespace std; int t,m; int c[105],v[105]; int dp[105][1005]; int main(){ cin>>t>>m; for(int i=1;i<=m;i++){ cin>>c[i]>>v[i]; } for(int i=1;i<=m;i++){ for(int j=1;j<=t;j++){ dp[i][j] = dp[i-1][j]; if(j>=c[i]) dp[i][j] = max( dp[i-1][j] , dp[i-1][j-c[i]]+v[i]); } } cout<<dp[m][t]; return 0; }

二维dp： 一维：

AC代码： #include<bits/stdc++.h> using namespace std; int m,t; int c[101]; int v[101]; int dp[101][1001]; int main(){ cin >> t >> m; for(int i = 1;i <= m;i ++){ cin >> c[i] >> v[i]; } for(int i = 1;i <= m;i ++){ for(int j = 1;j <= t;j ++){ dp[i][j] = dp[i-1][j]; if(j >= c[i]) dp[i][j] = max(dp[i-1][j] , dp[i-1][j-c[i]] + v[i]); } } cout << dp[m][t]; return 0; }