题目：小明的背包1（蓝桥OJ 1174）

本文主要是介绍题目：小明的背包1（蓝桥OJ 1174），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

 

---

解题思路：

        01背包模板题 

---

题解：

// 未优化的01背包
// #include <bits/stdc++.h>
// using namespace std;
// using ll = long long;
// const int N = 1e2 + 9, M = 1e3 + 9;
// int a[N][M];
// ll dp[N][M];// int main()
// {
//   int n, V;cin >> n >> V;
//   for(int i = 1; i <= n; i++)
//   {
//     int w, v;cin >> w >> v;
//     for(int j = 0; j <= V; j++)
//     {
//       if(j >= w)dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v);
//       else dp[i][j] = dp[i - 1][j];
//     }
//   }//   cout << dp[n][V] << '\n';
//   return 0;
// }//优化dp成一维
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e2 + 9, M = 1e3 + 9;
int a[N][M];
ll dp[M];int main()
{int n, V;cin >> n >> V;for(int i = 1; i <= n; i++){int w, v;cin >> w >> v;for(int j = V; j >= w; j--){dp[j] = max(dp[j], dp[j - w] + v);}}cout << dp[V] << '\n';return 0;
}

---

知识点：01背包，动态规划 

这篇关于题目：小明的背包1（蓝桥OJ 1174）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---