01背包dp问题

本文主要是介绍01背包dp问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

E-来硬的_牛客小白月赛92 (nowcoder.com)

赛时没有看出来，赛后回顾一下值域比较小，有容量有价值，就是一个01背包..

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[1000010][2];
void solve() {int n, m;cin >> n >> m;memset(dp, 0x3f, sizeof dp);dp[0][0] = dp[0][1] = 0;for (int i = 1; i <= n; i ++) {int x, y;cin >> x >> y;for (int j = m; j >= 0; j --) {dp[j][0] = min(dp[j][0], dp[max(0ll, j - x)][0] + y);dp[j][1] = min(dp[j][1], dp[max(0ll, j - x)][1] + y);dp[j][1] = min(dp[j][1], dp[max(0ll, j - 2 * x)][0] + y / 2);}}cout <<  dp[m][1] << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;t = 1;//std::cin >> t;while (t--) {solve();}return 0;
}

这篇关于01背包dp问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---