绝对的水题，只是用来复习。

本题在洛谷上的链接：

---

 这不就是最简单的01背包吗？虽然每件物品的重要度变成了输入的重要度*物品价格。

01背包没什么好说的，多写两遍就会了，最朴素的01背包时间复杂度是O(n*m)的，空间复杂度也是O(n*m)的。原因在于此时的状态转移方程为dp[i][j]=max(dp[i-1][j],dp[i-1][j-p[i]]+v[i])，每次我们处理完一件物品时，数组中存放的就是上一件物品的dp值，如果可以加以利用，就可以省去一维。我们可以逆序枚举j，这样dp[j]=max(dp[j],dp[j-p[i]]+v[i])，每当我们处理到dp[j]时，此时的dp[j]中存放的其实就是dp[i][j]。时间复杂度就很难优化了。

1 #include 
      
        2  3 const int maxn = 3e4 + 5, maxm = 30; 4  5 int v[maxm], p[maxm], dp[maxn]; 6  7 int main() { 8     int n, m; 9     scanf("%d%d", &n, &m);10     for (int i = 1; i <= m; ++i) {11         scanf("%d%d", &v[i], &p[i]);12         for (int j = n; j >= v[i]; --j)13             if (dp[j] < dp[j - v[i]] + v[i] * p[i])14                 dp[j] = dp[j - v[i]] + v[i] * p[i];15     }16     printf("%d", dp[n]);17     return 0;18 }