6.2 开心的金明
题目链接
题目思路
01背包问题,把+v[i]换成了+v[i]*w[i]
代码实现
#include<bits/stdc++.h> using namespace std; const int Max=30; int v[Max],w[Max]; int dp[Max][30005]; int main() { int n,m; cin>>m>>n; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; for(int i=1;i<=n;i++) for(int j=m;j>=0;j--) { if(v[i]>j) dp[i][j]=dp[i-1][j]; else dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+v[i]*w[i]); } cout<<dp[n][m]<<endl; return 0; }