用01背包算法解决P1060 开心的金明问题,并附详细注释
时间: 2024-04-08 14:30:56 浏览: 15
当然,下面是使用01背包算法解决P1060 开心的金明问题的代码,并附有详细注释:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 33000; // 背包最大容量
int dp[MAXN]; // 动态规划数组,dp[i]表示容量为i时的最大价值
int main() {
int n, m; // n表示物品个数,m表示背包容量
cin >> m >> n;
for (int i = 0; i < n; i++) {
int v, p; // v表示物品的体积,p表示物品的价值
cin >> v >> p;
for (int j = m; j >= v; j--) {
// 从后往前遍历背包容量,保证之前计算的dp[j-v]没有被覆盖
dp[j] = max(dp[j], dp[j - v] + v * p);
// 更新当前容量下的最大价值
}
}
cout << dp[m] << endl; // 输出背包容量为m时的最大价值
return 0;
}
```
代码解释:
1. 首先,我们定义了常量MAXN表示背包的最大容量,并声明了一个长度为MAXN的dp数组,dp[i]表示容量为i时的最大价值。
2. 接下来,从输入中读取背包容量m和物品个数n。
3. 然后,使用一个循环遍历每个物品。在每次循环中,我们读取当前物品的体积v和价值p。
4. 接着,使用一个逆序的循环遍历背包容量j,从m到v。这样做是为了保证之前计算的dp[j-v]没有被覆盖。
5. 在内层循环中,我们更新dp[j]的值,将其更新为dp[j]和dp[j-v] + v * p的较大值。其中,dp[j]表示不选当前物品时的最大价值,dp[j-v] + v * p表示选择当前物品时的最大价值。
6. 最后,输出dp[m],即背包容量为m时的最大价值。
希望这个解释对你有帮助!如果还有其他问题,请随时提问。