还是一个背包问题。只是在这里需要计算的价值变成了每件物品的价格与重要度的乘积。
但是由于价格和重要度的乘积的总和较大，所以采用离散化的方式去减少空间。由于没有结果的不需要记录，如果当前选的结果还没有之前没选的大也不用更新。
使用map去保存从而减少的空间。 
#include <bits/stdc++.h>

using namespace std;
const int maxn = 30;
struct Node {
    int price;
    int importance;
    int total = price*importance;
};
//做一个离散化的处理
map<int, int> dp;
int N, m;
Node a[maxn];

int main() {
    cin>>N>>m;
    for (int i=1;i<=m;i++) {
        cin>>a[i].price>>a[i].importance;
        a[i].total = a[i].price*a[i].importance;
    }
    for (int i=1;i<=m;i++) {
        for (int j=N;j>=0;j--) {
            if (j>=a[i].price) {
                if (dp[j-a[i].price]+a[i].total > dp[j]) {
                    dp[j] = dp[j-a[i].price]+a[i].total;
                }
            }
        }
    }
    map<int, int>::iterator it = dp.end();
    it--;
    cout<<(*it).second;
    return 0;
}