我们有 3 克、5 克、7 克三种重量的砝码,每种都有无穷多个。 现在要凑出总重恰好 N 克,最多可以使用多少个砝码? 如果凑不出 N 克,输出 -1。 c++递推,无其他头文件适合初学者理解无INT_MAX
时间: 2024-04-21 20:23:30 浏览: 30
下面是一个使用递推方法解决凑重量问题的 C++ 代码,不需要使用 `INT_MAX`,适合初学者理解。
```cpp
#include <iostream>
using namespace std;
int maxNumOfWeights(int N) {
int maxNum[N + 1];
int weights[] = {3, 5, 7};
maxNum[0] = 0; // 初始条件
for (int i = 1; i <= N; i++) {
maxNum[i] = -1; // 初始化为-1,表示无法凑出该重量
for (int j = 0; j < 3; j++) {
if (i >= weights[j] && maxNum[i - weights[j]] != -1) {
maxNum[i] = max(maxNum[i], maxNum[i - weights[j]] + 1);
}
}
}
return maxNum[N];
}
int main() {
int N;
cout << "请输入要凑出的总重量 N:";
cin >> N;
int result = maxNumOfWeights(N);
cout << "最多可以使用 " << result << " 个砝码凑出总重量为 " << N << " 克。" << endl;
return 0;
}
```
该代码使用一个数组 `maxNum` 来记录凑出不同重量所需的最多砝码数量。初始时,将 `maxNum[0]` 设置为 0,表示凑出重量为 0 克不需要砝码。然后从重量为 1 开始递推,对于每个重量,依次判断使用三种不同砝码重量时是否能凑出该重量。如果可以凑出,就更新 `maxNum[i]` 的值为凑出该重量使用的最多砝码数量。最后返回 `maxNum[N]`,即凑出总重量为 N 克所需的最多砝码数量。如果无法凑出总重量为 N 克,则返回 -1。
希望这个代码能够帮助到你!