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

题目描述：P1060 [NOIP2006 普及组] 开心的金明

---

解题思路

---

• 解题思路

  1、简单分析可知该题为 01 背包 问题。可看作容量为 $n$ 的背包，有 $m$ 种物品，每种物品体积为 $v$，价值为 $v * w$
  2、确定状态：令 $dp[i]$ 表示到当前为止花费了 $i$ 元的最大价值
  3、确定转移：同 01 背包 的状态转移，$dp[j] = max(dp[j], dp[j - v[i]] + w[i])$

---

代码实现

---

• 代码实现

  #include <bits/stdc++.h>
  using namespace std;
  
  const int N = 1e5 + 10, M = 100;
  int dp[N];      // 一维 01 背包，dp[i] 表示到目前为止花费 i 元的最大价值
  int v[M], w[M]; // v[i] 为代价，w[i] 为价值，其中 w[i] = v * w;
  
  void solve()
  {
      int n, m;
      cin >> n >> m;
      for (int i = 1; i <= m; i++)
      {
          int v_, w_;
          cin >> v_ >> w_;
          v[i] = v_;
          w[i] = v_ * w_;
      }
  
      // 一维 01 背包
      for (int i = 1; i <= m; i++)
          for (int j = n; j - v[i] >= 0; j--)
              dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
  
      cout << dp[n] << endl;
  }
  
  int main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      int T = 1;
      // cin >> T;
      while (T--)
          solve();
      return 0;
  }

---

页底评论

---