背包问题 2

背包问题 2

描述

n 个物品，每个物品有一个体积 v 和价值 w。现在你要回答，把一个物品丢弃后，剩下的物品装进一个大小为 V 的背包里能得到的最大价值是多少。

输入

输入的第一行包含一个正整数 n（n ≤ 5000）。

接下来 n 行，每行包含两个正整数 v 和 w（v,w ≤ 5000），分别表示一个物品的体积和价值。

接下来一行包含一个正整数 q（q ≤ 5000）,表示询问个数。

接下来 q 行，每行包含两个正整数V 和x（V ≤ 5000，x ≤ n），表示询问将物品 x 丢弃以后剩下的物品装进一个大小为V 的背包能得到的最大价值。

输

输出q 行，每行包含一个整数，表示询问的答案。

样例 1 输入

3

35

22

12

3

31

32

33

样例 1 输

样例 1 解释

有 3 个物品，第一个物品的体积为 3、价值为 5，第二个物品体积为 2、价值为 2，第三个物品体积为 1、价值为 2。

有 3 个询问：

第一个询问是问去掉 1 物品后剩下的 2、3 物品填进一个大小为 3 的背包能得到的最大价值。显然 2、3 物品都是可以放进背包的，所以最大价值为 2+2=4。

第二个询问是问去掉 2 物品后剩下的 1、3 物品填进一个大小为 3 的背包能得到的最大价值。若我们填 3 物品，我们只能得到价值 2；若我们填 1 物品，则可以得到价值 5。所以最大价值为 5。

第三个询问我们同样也是填 1 物品，最大价值为 5。

样例 2

请查看下发文件内的 sample2_input.txt 和 sample2_output.txt。

限制

对于 30%的数据，n,q,v,V,w ≤ 10； 对于 50%的数据，n,q,v,V,w ≤ 200。时间：10 sec

空间：512 MB

提示

[我们可以预处理“前缀背包”、“后缀背包”，然后询问时做“背包合并”的操作。]

代码

#include <iostream> #include<vector> #include<algorithm>

#pragma warning(disable:4996) using namespace std;

// ================= 代码实现开始 =================

/* 请在这里定义你需要的全局变量 */ const int N = 5005;

//d:前缀背包,d[i][j]表示物品1到物品i放进容量j的背包中的最大价值

//f:后缀背包,f[i][j]表示物品i到物品n放进容量j的背包中的最大价值int d[N][N], f[N][N];

// n个物品，每个物品有体积价值，求若扔掉一个物品后装进给定容量的背包的最大价值

// n：如题

// w：长度为n+1的数组，w[i]表示第i个物品的价值（下标从1开始，下标0是一个数字-1，下面同理）

// v：长度为n+1的数组，v[i]表示第i个物品的体积

// q：如题

// qV：长度为q+1的数组，qV[i]表示第i次询问所给出的背包体积

// qx：长度为q+1的数组，qx[i]表示第i次询问所给出的物品编号

// 返回值：返回一个长度为q的数组，依次代表相应询问的答案

vector<int> getAnswer(int n, vector<int> w, vector<int> v, int q, vector<int> qV, vector<int> qx) {

/* 请在这里设计你的算法 */

//计算前缀背包

for (int i = 1; i <= n; ++i)

{

for (int V = 0; V < v[i]; ++V)

d[i][V] = d[i - 1][V];//此处copy是为了使得i+2,i+3...行需要使用的时候能够直接调用数据

for (int V = v[i]; V <= 5000; ++V)

d[i][V] = max(d[i - 1][V], d[i - 1][V - v[i]] + w[i]);

}

//计算后缀背包

for (int i = n; i >= 1; --i)

{

for (int V = 0; V < v[i]; ++V)

f[i][V] = f[i + 1][V];

for (int V = v[i]; V <= 5000; ++V)

f[i][V] = max(f[i + 1][V], f[i + 1][V - v[i]] + w[i]);

}

vector<int> ans;

for (int k = 1; k <= q; ++k)

{

int x = qx[k], V = qV[k];

int mx = 0;//记录当前询问的最优答案

//抽去x，然后用前缀背包与后缀背包计算最优背包

for (int i = 0; i <= V; ++i)

{

mx = max(mx, d[x - 1][i] + f[x + 1][V - i]);

}

ans.push_back(mx);

}

return ans;

}

// ================= 代码实现结束 =================

int main() {

int n, q;

vector<int> v, w, qv, qx;

v.push_back(-1);

w.push_back(-1);

qv.push_back(-1);

qx.push_back(-1);

scanf("%d", &n);

for (int i = 0; i < n; ++i) {

int a, b;

scanf("%d%d", &a, &b);

v.push_back(a);

w.push_back(b);

}

scanf("%d", &q);

for (int i = 0; i < q; ++i) {

int a, b;

scanf("%d%d", &a, &b);

qv.push_back(a);

qx.push_back(b);

}

vector<int> ans = getAnswer(n, w, v, q, qv, qx);

for (int i = 0; i < q; ++i)

printf("%d\n", ans[i]);

return 0;

}