开心的金明

先看题目：https://ac.nowcoder.com/acm/problem/16666
题目描述：
从m个物品中挑选，希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
解题思路：
01背包，只不过这里dp[][]记录的是价格与重要度的乘积而不是能够塞下物品的数量
代码：

#include<bits/stdc++.h>
using namespace std;
int v[30],w[30],dp[30010];
int main()
{
    int n, m;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; i++) {
        scanf("%d%d",&v[i],&w[i]);
    }
    for(int i = 1; i <= m; i++)
    for(int j = n; j >= v[i]; j--) {
        dp[j] = max(dp[j], dp[j-v[i]]+v[i]*w[i]);
    }
    printf("%d\n",dp[n]);
}