#include <cstdio> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> #include <map> #include <vector> #include <set> #include <stack> #include <queue> using namespace std; typedef long long ll; int v[30]; int w[30]; int dp[30][30005]; int n,m; int main ()//和经典的01背包基本一模一样； { cin >>n>>m; memset(dp,0,sizeof dp); for(int i=0;i<m;i++) { int vv,p; cin >>vv>>p;//分别输入价格和重要度 v[i]=vv;//价格储存 w[i]=vv*p;//两者乘积储存 } for(int i=0;i<m;i++)//从第一个物品开始 { for(int j=0;j<n;j++) { if(v[i]>j)//当此时的钱小于该物品的价格说明当钱为j时不能买第i个物品，则此时状态就等于上一个状态 dp[i+1][j]=dp[i][j];//dp[i+1][j]表示当买i物品时手中有j钱，不够，则不买 else//如果此时的钱能买第i个物品，那么就判断买还是不买那个得到的价值更大 dp[i+1][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);//dp[i][j]是没有买这个物品，如果买了就让现在的钱j减去物品的价格 //如j-v[i]，然后判断dp[i][j-v[i]]第i-1个商品能否用j-v[i]钱买到，买到的话就是他的价值加上此时这个商品的价值 //然后判断买当前商品和不买当前商品所得到的价值那个比较大； //如果其中一个j能满足当前这个商品的价格，并且减去当前商品价格后还能买得起之前的i-1个商品，那么以后的j都符合要求 } } cout <<dp[m][n-1]<<endl;//数组dp[m][n-1]表示当买完第m个商品时，并且假设第m-1个商品用n个钱买的时候所得到的最大价值 return 0; }