P1049 装箱问题

确认所需算法

题目链接：P1060 开心的金明

这题是一道01背包问题，如果你还不知道什么是背包问题，那么请看我的背包问题学习笔记

思路

这道题的输入有一点点奇怪，v[i] = 2~n+1行的第一个数*第二个数。其他的稍微抽象一点就可以变为标准的01背包问题了。关于状态转移方程的推导，可以参考我这篇文章P1049题解。

代码

#include<cstdio>
#include<stack>
#include<iostream>
using namespace std;
long long vv,n,w[50],v[50],f[30010];
int main(){
    cin >> vv >> n;
    for (int i = 1;i <= n;++i) cin >> w[i] >> v[i],v[i] *= w[i];
    for (int i = 1;i <= n;++i){
        for (int j = vv;j >= w[i];--j){
            f[j] = max(f[j],f[j - w[i]] + v[i]);
        }
    }
    cout << f[vv];
    return 0;
}