---
title: "开心的金明"
created: 2025-11-28
tags:
  - 算法
---

# 开心的金明

## 题目 [开心的金明](https://www.acwing.com/problem/content/description/428/)

![[image-64481155.png]]

## 思路分析

裸题

限制条件v变成了价格 权重w变成了重要度

注意这个重要度是需要w[i]=w[i]\*v[i]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=30010;

int v[N],w[N];//此时v为价格（限制条件） w为重要度

int dp[N];

int n,m;

int main()

{

    cin>>m>>n;

    for(int i=1;i<=n;i++){

        cin>>v[i]>>w[i];

        w[i]=w[i]*v[i];

    }

    for(int i=1;i<=n;i++)

        for(int j=m;j>=v[i];j--)

            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

    cout<<dp[m];

    return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=30010;

int dp[N];

int n,m;

int main()

{

    cin>>m>>n;

    for(int i=1;i<=n;i++){

        int v,w;//vw也可以不用存下来

        cin>>v>>w;

        w=w*v;

        //其实可以合并

        for(int j=m;j>=v;j--)

            dp[j]=max(dp[j],dp[j-v]+w);

    }

    cout<<dp[m];

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[01背包练习|01背包练习]] 🏠 [[00-刷题理模型]] ➡️ [[数字组合|数字组合]]