思路:动态规划的背包问题。建立二维数组dp[i][j]表示前i个物品不超过j元物品的价格与重要度乘积的总和的最大值。dp[i][j]=max(dp[i-1][j],dp[i-1][j-V[i]]+V[i]*W[i]) 特殊情况:当j<v[i]时,dp[i][j]=dp[i-1][j]。
注意:可以不用初始化,当申请的数组为全局数组,不赋值默认值为0;
#include "iostream" #include "algorithm" using namespace std; int V[26]; int W[26]; long long int dp[26][30001]; int main() { int N,n,i,x; cin>>N>>n; for(i=1;i<=n;i++){ cin>>V[i]>>W[i]; } for(i=1;i<=n;i++){ for(int j=N;j>=1;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][N]; }