problem

• 有n个物品，价格为wi, 重要度为vi。
• 在代价不超过m的情况下，最大化wi*vi的值
• n < 30, m < 3e4

solution

Qwq，Wi*Vi是确定的。

所以vi *= wi;之后，，，就是一个01背包。

——

f[i]表示剩余体积为i时能获得的最大价值

决策过程可以选或者不选。

更多见背包九讲？

复杂度O(mn)

codes

#include
    
     using namespace std;const int maxn = 40;int v[maxn], w[maxn], f[50005];int main(){    int n, m;  cin>>m>>n;    for(int i = 1; i <= n; i++){        int x, y;   cin>>x>>y;        w[i] = x;  v[i] = x*y;    }    for(int i = 1; i <= n; i++)        for(int j = m; j >= w[i]; j--)            f[j] = max(f[j], f[j-w[i]]+v[i]);    cout<
     
      <<'\n';    return 0;}