开心的金明（动态规划，dp，背包）

思路:动规01背包问题，注意计算价值时有一个价格和重量度的乘积计算

方法一：二维背包

#include<iostream> #include<string> #include<algorithm> using namespace std; int dp[30][30005]; int v[10000],w[100005]; int n,m; int main(){ cin>>n>>m; ///输入 for(int i=1;i<=m;i++){ cin>>v[i]>>w[i]; } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ dp[i][j]=dp[i-1][j]; if(j>=v[i]){ dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]*v[i]); } } } cout<<dp[m][n]<<endl; return 0; }

方法二：一维背包

#include<iostream> #include<string> #include<algorithm> using namespace std; int dp[100005],v,w,n,m; int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ cin>>v>>w; for(int j=n;j>=v;j--){ dp[j]=max(dp[j],dp[j-v]+w*v); } } cout<<dp[n]; return 0; }