C++解决钢条切割问题【动态规划】

问题描述：

给定一根长度为 $l$ 的钢条$(l<=10000)$，以及一张价格表，请计算这根钢条能卖出的最大总收益。
价格表表示为 $(l_i,p_i)$，$1<=i<=k$。
不在价格表中的钢条可卖出价格为$0$。

思路：

根据动态规划的思想，我们可以构建一个数组 $dp$，其中 $dp[n]$ 代表了当总钢条长度为 $n$ 时所能卖出的最大价值，则递推式显然如下：

$$dp[n]=\underset{1<=i<=k}{\max }(p_i+dp[n-l_i])whenn>=l_i$$
$$dp[n]=0whenn<l_{i...k}$$

而初始化时，只需要将$dp[0,...,minLength]$设置为$0$即可。

源代码：

//
// main.cpp
// SteelCutting
//
// Created by 胡昱 on 2021/11/11.
//

#include <iostream>
#include <vector>
using namespace std;

class Steel{
    
public:
    int length;
    int value;
    Steel(int l, int v) {
    
        length = l;
        value = v;
    }
};

int main() {
    
    // 共m个问题
    int m;
    cin >> m;
    while((m--) > 0) {
    
        // 输入总钢条长度和价格表中不同价格的钢条的数量
        int l = 10000, c = 100;
        cin >> l >> c;
        
        // 构建动态规划数组
        // dp[i]代表了当总钢条长度为i时的最大产出价值
        int* dp = new int[l + 1];
        
        // 输入钢条长度价格表（如果长度超出了总钢条长度则不用输入）
        vector<Steel> steel;
        int length, value, minLength = 2147483647;
        for(int i = 0; i < c; ++i) {
    
            cin >> length >> value;
            if(length <= l) {
    
                
                steel.push_back(Steel(length, value));
                minLength = min(minLength, length);
            }
        }
        
        // 如果不能切出任何钢条则直接输出0
        if(steel.empty()) {
    
            cout << 0 << endl;
            continue;
        }
        
        // 进一步初始化动态规划数组
        for(int i = 0; i < minLength; ++i) {
    
            dp[i] = 0;
        }
        
        // 开始自底向上动态规划
        for(int li = minLength; li < l + 1; ++li) {
    
            int tempValue = 0;
            for(int i = 0; i < steel.size(); ++i) {
    
                if(steel[i].length <= li) {
    
                    tempValue = max(tempValue, steel[i].value + dp[li - steel[i].length]);
                }
            }
            dp[li] = tempValue;
        }
        
        cout << dp[l] << endl;
        delete [] dp;
    }
}