这个half为什么会变的

Question

#c++#动态规划#改错
在写动态规划作业题的时候遇到了这样的情况：

这个half为什么会变的？

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

您想要解决的问题

您提问的目的是解决在编写C++动态规划作业题时遇到的一个问题，即在代码执行过程中变量half的值发生了变化，导致程序结果不正确。

图片内容

图片中包含了一段C++代码，这段代码是关于动态规划的一个问题，涉及到一个数组f的初始化和计算，以及一个变量sum和half的计算。

问题出现原因

根据您提供的代码和错误信息，问题可能出现在以下几个方面：

1. 变量half的计算：half = sum / 2; 这行代码使用了整数除法，如果sum是奇数，half将丢失余数，导致实际的half值与预期不符。
2. 数组f的初始化：int f[n+1][5001] = {0}; 这行代码试图初始化一个二维数组，但是C++不支持这种形式的数组初始化。这可能导致未定义行为。
3. 数组w的读取：cin >> w[i]; 这行代码用于读取数组w的元素，但是没有提供w的初始化代码，可能导致未定义行为。

问题解决方案

1. 修正half的计算：使用整数除法时，应确保sum为偶数，或者使用浮点数除法并向下取整。
2. 正确初始化数组f：应使用循环或正确的方式来初始化数组。
3. 确保数组w正确初始化和读取：在读取w[i]之前，确保w已经被正确地初始化。

提供代码

以下是修改后的代码示例，包括对half的计算和数组初始化的修正：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, sum = 0;
    cin >> n;
    vector<vector<int>> f(n + 1, vector<int>(5001, 0));
    vector<int> w(n);
    
    for (int i = 1; i <= n; i++) {
        cin >> w[i - 1];
        sum += w[i - 1];
    }
    
    int half = sum / 2;
    if (sum % 2 != 0) {
        half--; // 如果sum是奇数，half需要减1
    }
    
    cout << "1:" << half << endl;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= half; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= w[i - 1] && f[i][j] < f[i - 1][j - w[i - 1]] + w[i - 1]) {
                f[i][j] = f[i - 1][j - w[i - 1]] + w[i - 1];
            }
        }
    }
    
    cout << "2:" << half << endl;
    cout << sum << " " << f[n][half] << endl;
    return 0;
}

代码运行方式

• 需要一个C++编译器，如g++。
• 编译命令：g++ -o program main.cpp
• 运行命令：./program

代码预期运行结果

1:half的值
2:half的值
sum f[n][half]的值

推荐相关链接

• C++动态规划基础
• C++数组初始化
• C++输入输出