题解：P1060 [NOIP2006 普及组] 开心的金明

· · 题解

solution

01 背包问题。

记 w_i 表示 v_i \times p_i，即物品 i 占用的背包容量，设 f_{i, j} 表示前 i 个物品容量为 j 的背包的最大价值。

考虑转移。假设当前已经处理好了前 i-1 个物品的所有状态，那么对于第 i 个物品，当其不放入背包时，背包的剩余容量和总价值都不变，故这种情况的最大价值为 f_{i-1, j}；当其放入背包时，背包的剩余容量会减小 w_i，背包中物品的总价值会增大 v_i，故这种情况的最大价值为 f_{i-1, j-w_i}+v_i。

综上，转移是 f_{i, j}=\max(f_{i-1, j}, f_{i-1, j-w_i}+v_i)。

由于对物品 i 影响的只有物品 i-1，所以我们可以去掉一维，用 f_j 表示容量为 j 的背包的最大价值，转移是 f_j=\max(f_j, f_{j-w_i}+v_i)。

最后我们注意枚举顺序，是从大到小的，否则则会出现一个物品多次放入背包的情况。

code

#include<bits/stdc++.h>
using namespace std;
int n, m, f[30001], v[30], p[30];
int main(){
    cin >> n >> m;
    for(int i=1; i<=m; i++)
        cin >> v[i] >> p[i],
        p[i]*=v[i];
    for(int i=1; i<=m; i++)
        for(int j=n; j>=v[i]; j--)
            f[j]=max(f[j], f[j-v[i]]+p[i]);
    cout << f[n];
    return 0;
}