C++ 海盗寻宝：最小价值背包问题

C++:判题描述最努的加利海货的杰克船长驿驿着他的黑珍球号海货船&#uff0c;找到了一个装满宝货的藏宝洞。藏宝洞里面有N(N≤100)堆金币&#uff0c;第i堆金币的总重量和总价值分别是mi,vi(1≤mi,vi≤100)。黑珍球号的承重量为T(T≤1000)。为了长远发展&#uff0c;所以他决定带走尽可能少价值的金币&#uff0c;但是他要求必须装满。所有金币都可以任意分割&#uff0c;分割完的金币重量价值比(&x5c31;是单位价值)不变。请问杰克船长最少可以拿走多少价值的金币?

输入描述第一行两个整数N、T。

接着N行&#uff0c;每行两个整数mi、vi。

输出描述一个实数表示答案&#uff0c;保留两位小数。

样本1输入4 5010 6020 10030 10015 45 输出170.00提示无内容&#uff1a;首先&#uff0c;我们可以将这个问题转化为一个背包问题。考虑到杰克船长要求装满背包&#uff0c;我们可以使用动态计算来解决。

首先&#uff0c;我们可以定义一个二维数组dp&#uff0c;在此dp[i][j]表示前i堆金币装入承重量为j的背包时&#uff0c;能够取得的最小总价值。

对于每一堆金币&#uff0c;我们有两种选择&#uff1a;装入背包或者不装入背包。如果我们选择装入第i堆金币&#uff0c;那么背包的剩余承重量为 j - mi&#uff0c;所以我们可以更新dp[i][j]为 dp[i-1][j-mi] + vi。如果我们选择不装入第i堆金币&#uff0c;那么背包的剩余承重量为 j&#uff0c;所以我们可以更新dp[i][j]为 dp[i-1][j]。

最后&#uff0c;dp[N][T]就表示了杰克船长能够拿走的最少价值的金币。

下面是C++的代码实现&#uff1a;cpp#include #include #include

using namespace std;

double pirateTreasure(int N, int T, vector& m, vector& v) { vector<vector> dp(N+1, vector(T+1, 0.0));

for (int i = 1; i <= N; i++) {        for (int j = 1; j <= T; j++) {            if (j >= m[i-1]) {                dp[i][j] = max(dp[i-1][j], dp[i-1][j-m[i-1]] + v[i-1]);            } else {                dp[i][j] = dp[i-1][j];            }        }    }

return dp[N][T];}

int main() { int N, T; cin >> N >> T;

vector<int> m(N);    vector<int> v(N);

for (int i = 0; i < N; i++) {        cin >> m[i] >> v[i];    }

double result = pirateTreasure(N, T, m, v);    cout << fixed << setprecision(2) << result << endl;

return 0