[NOIP 2006 普及组] 开心的金明

知识点

动态规划、01背包

解题思路

每件商品的价值为价格v乘重要度p，容量消耗为v。按预算倒序做01背包，得到不超过预算的最大总价值。

正确性说明

每件商品选或不选构成互斥且穷尽的两类方案，容量倒序确保选当前商品时使用的是此前商品的最优值。根据01背包归纳，最终得到最优购物单价值。

易错点

不是只比重要度或价格；可以不花完预算；0价格商品价值也为0，每件仍只能选一次。

复杂度

时间O(nm)，空间O(n)，n为预算、m为商品数。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int n,m;cin>>n>>m;vector<int>dp(n+1);while(m--){int v,p;cin>>v>>p;for(int c=n;c>=v;c--)dp[c]=max(dp[c],dp[c-v]+v*p);}cout<<dp[n]<<'\n';}