C++实现用动态规划思想解决1/0背包问题

问题描述：
有一个容量为C(C<=100)的背包。
现在你手边有N(N<=500)颗宝石，第i颗宝石大小为si，价值为vi。
由于条件限制，你手边只有这个背包可作为你搬运宝石的唯一工具。
现在你想知道在这样的条件下你最多可以带走多大利润的宝石。

输入示例：
3
3 10
1 3 2 5 7 2
3 10
1 3 2 5 6 2
5 10
5 6 5 7 2 8 8 1 5 9

输出示例：
10
10
17

思路：
有空再写

源代码：

//
// main.cpp
// PackageProblem
//
// Created by 胡昱 on 2021/11/8.
//

#include <iostream>
using namespace std;

struct Gemstone{
    
    int weight;
    int value;
};

int main() {
    
    // 共m个问题
    int m;
    cin >> m;
    while((m--) > 0) {
    
        // 输入宝石数量和背包大小
        int n = 500, c = 100;
        cin >> n >> c;
        
        // 创建宝石数组并初始化
        Gemstone* gemstones = new Gemstone[n];
        int minWeight = 2147483647;
        for(int i = 0; i < n; ++i) {
    
            cin >> gemstones[i].weight >> gemstones[i].value;
            minWeight = gemstones[i].weight < minWeight ? gemstones[i].weight : minWeight;
        }
        minWeight = minWeight < 1 ? 1 : minWeight;
        
        // 初始化动态规划所需使用的辅助数组dp
        // dp[i][j]指的是当背包容量为j时能够带走的最大宝石价值（此时仅考虑宝石[0, ..., i]）
        int** dp = new int*[n];
        for(int i = 0; i < n; ++ i) {
    
            dp[i] = new int[c + 1];
            for(int j = 0; j < minWeight; ++j) {
    
                dp[i][j] = 0;
            }
        }
        for(int j = 0; j < c + 1; ++j) {
    
            dp[0][j] = (gemstones[0].weight <= j) ? gemstones[0].value : 0;
        }
        
        // 开始动态规划
        for(int i = 1; i < n; ++i) {
    
            for(int j = minWeight; j < c + 1; ++j) {
    
                if(gemstones[i].weight <= j) {
    
                    if(dp[i - 1][j] > gemstones[i].value + dp[i - 1][j - gemstones[i].weight]) {
    
                        dp[i][j] = dp[i - 1][j];
                    }
                    else {
    
                        dp[i][j] = gemstones[i].value + dp[i - 1][j - gemstones[i].weight];
                    }
                }
                else {
    
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        
        // 输出结果并释放资源
        cout << dp[n - 1][c] << endl;
        for(int i = 0; i < n; ++i) {
    
            delete [] dp[i];
        }
        delete [] dp;
    }
}