今日题目：金明的背包
题目分析
题目难度：⭐️
题目涉及算法：dp。
ps：有能力的小伙伴可以尝试优化自己的代码或者一题多解，这样能综合提升自己的算法能力
题解报告：
1.思路
这种有限制的买东西的一般都是背包问题，背包问题很大一部分考的都是模板，大家应该都学过背包，没有学过的话去学一下吧，这个东西不是很难，也没有什么好讲的，直接上代码，代码有备注
2.代码
#include<bits/stdc++.h> using namespace std; int w[30],v[30],dp[100001];//w数组为重要度，v数组为钱 int n,m;//n是总物品个数，m是总钱数 int main() { cin>>m>>n; for(int i=1;i<=n;i++) { cin>>v[i]>>w[i]; w[i] *= v[i];//根据题意 } for(int i=1;i<=n;i++) { for(int j=m;j>=v[i];j--)//01背包要倒着 { if(j>=v[i]) { dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//dp } } } cout<<dp[m];//背包大小为m时最大值 return 0; }
