<---- 麻烦点一下旁边向上的三角形

推销一下：

$\color{#00FF7F}{算法提高课 第一章 动态规划 全题解（正在完善）}$

题目描述

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

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

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

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

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

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

设第 $j$ 件物品的价格为 $v[j]$，重要度为 $w[j]$，共选中了 $k$ 件物品，编号依次为 $j1，j2，…，jk$，则所求的总和为：

$$v[j_1]×w[j_1]+v[j_2]×w[j_2]+…+v[j_k]×w[j_k]$$
请你帮助金明设计一个满足要求的购物单。

输入格式

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

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

输出格式

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

数据范围

$1≤N<30000$,
$1≤m<25$,
$0≤v≤10000$,
$1≤p≤5$

输入样例：

1000 5
800 2
400 5
300 5
400 3
200 2

输出样例：

3900

这一题乍看上去像01背包（废话☺）
可它就是01背包啊

我们发现：

乍一看没有价格啊
其他都和01背包一样
所以…
我们可以像装箱问题那样转换一下：

最后它要输出价格乘重要度
那我们是不是可以把它看成价值呢
答案是可以

现在就可以开始转换了

我们可以做这样的转换：

总钱数看成背包总容量；
每件物品的价格看成体积；
每件物品的价格乘以重要度看成价值；

好了，如果你还不知道01背包的话可以去看一下我01背包的良心题解。

算法1

(二维动态规划) $O(n^2)$

74我了，为了写题解，特意去写了二维的方法，调了半天，都是运行时错误。
后来发现是因为$N$开太大了
已修正，请放心食用

注意：

不要把f,w,v偷懒直接写上30010要不然就犯了我这种蒟蒻犯的错误

时间复杂度

两层循环， $O(n^2)$

参考文献

C++ 代码

#include <iostream> 
#include <algorithm>
using namespace std;
const int N = 30010,M = 30; //注意啦~
int money,n; //分别代表妈妈给的钱和想买的物品数量
int f[M][N]; //状态转移
int v[M]; //每个物品的价格
int w[M]; //每个物品的重要度，但是后面会改成价值
int main(){
    scanf("%d%d",&money,&n); //输入妈妈给的钱和想买的物品数量
    for(int i = 1;i <= n;i ++){ //读入每个物品的价格和重要度
        scanf("%d%d",&v[i],&w[i]); //读入
        w[i] *= v[i]; //因为后面w数组被我们魔改成了价值，所以要乘上v
    }
    for(int i = 1;i <= n;i ++){
        for(int j = 0;j <= money;j ++){
            f[i][j] = f[i - 1][j]; //不选，直接等于上一次的结果
            if(v[i] < j) f[i][j] = max(f[i][j],f[i - 1][j - v[i]] + w[i]); //和01背包的状态转移没区别了
        }
    }
    printf("%d\n",f[n][money]); //输出
    return 0;
}

算法2

(滚动数组优化) $O(n^2)$

只要你理解了前面的代码，你这个就很容易理解了

思路请看我01背包的良心题解。

时间复杂度

参考文献

C++ 代码

使用&运算

#include <iostream> 
#include <algorithm>
using namespace std;
const int N = 30010,M = 30;
int money,n;
int f[2][N];
int v[M];
int w[M];
int main(){
    scanf("%d%d",&money,&n);
    for(int i = 1;i <= n;i ++){
        scanf("%d%d",&v[i],&w[i]);
        w[i] *= v[i];
    }
    for(int i = 1;i <= n;i ++){
        for(int j = 0;j <= money;j ++){
            f[i & 1][j] = f[i - 1 & 1][j];
            if(v[i] < j) f[i & 1][j] = max(f[i & 1][j],f[i - 1 & 1][j - v[i]] + w[i]);
        }
    }
    printf("%d\n",f[n & 1][money]);
    return 0;
}

算法3

(一维$01$背包) $O(nm)$

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30010;
int money,n;
int v[N],w[N];
int f[N];
int main(){
    scanf("%d%d",&money,&n);
    for(int i = 1;i <= n;i ++){
        scanf("%d%d",&v[i],&w[i]);
        w[i] *= v[i];
    }
    for(int i = 1;i <= n;i ++){
        for(int j = money;j >= v[i];j --){
            f[j] = max(f[j],f[j - v[i]] + w[i]); //转换掉啦~
        }
    }
    printf("%d\n",f[money]);
    return 0;
}

（共210行）