开心的金明（DP）

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。

更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。

今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。

于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。

他还从因特网上查到了每件物品的价格（都是整数元）。

他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为

v [j 1] * w [j 1] + v [j 2] * w [j 2] + \dots + v [j k] * w [j k]

请你帮助金明设计一个满足要求的购物单。

输入格式

输入文件的第1行，为两个正整数N和m，用一个空格隔开。（其中N表示总钱数，m为希望购买物品的个数）

从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数v和p。（其中v表示该物品的价格，p表示该物品的重要度）

输出格式

输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（数据保证结果不超过100000000）。

数据范围

输入样例：

输出样例：

3900



01背包问题，需要注意的是要处理好重量与价值的关系。在这里把重要性看作是重量，
将v*p看作一个整体并把它们当做重量来处理，处理完后实际上展现在我们面前的数据如下：
　　　　w 　　　　　　v
　　　800　　　　　　800*2
　　　400　　　　　　400*5
　　   300　　　　　　300*5
　　　400　　　　　　400*3
　　　200　　　　　　200*2

然后dp即可算出答案
AC代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 30000+15;
typedef long long ll;
ll n,m;
ll f[30][N]; //注意如果用二维数组做，必须要限制要数组的边界，否则很可能溢出报错

struct node{
    ll v;  //单个物品的价值
    ll p;　//物品的重要性
    ll total;  //存储总价值
}a[35]; 

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i = 1;i<=m;++i){
        cin>>a[i].v>>a[i].p;
        a[i].total = a[i].v*a[i].p;
    }

for(int i = 1;i<=m;++i){
        for(int j = n;j>0;--j){
            f[i][j] = f[i-1][j];
            if(j>a[i].v){
                f[i][j] = max(f[i-1][j],f[i-1][j-a[i].v]+a[i].total);
            }
        }
    }
    cout<<f[m][n]<<endl;
    return 0;
}

当然有更好的办法，也可以将这个问题将转为一维问题，自己开动脑筋思考吧！！！