背包问题 1

背包问题 1

描述

n 种物品，每种物品有相应的价值和体积，同时物品还分为两类，一类是“单个物品”，即该种物品只有一个；一类是“多个物品”，即该种物品有无限个。

现在你有一个体积为 V 的背包，那么该装些什么物品到背包里使得价值之和最大呢？

输入

第一行包含两个正整数 n,V。

接下来 n 行，每行代表一种物品。每行的第一个数字表示该物品的种类（若为 0 表示“单个物品”，若为 1 表示“多个物品”），第二个数字表示该物品的价值，第三个数字表示该物品的体积。

输

输出一个整数，表示最大的价值之和。

样例 1 输入

样例 1 输

样例 1 解释

第三种物品有无限个，其余都是单个物品。

若我们放入物品 1，则背包已经装满，此时价值和为 6；

若我们放入物品 2、4、5，背包所剩体积为 8-3-1-2=2，此时价值和为 7+8+5=20； 若我们放入 8 个物品 3，背包装满，此时价值之和为 8×1=8；

若我们放入物品 2、4、5，再放两个物品 3，则背包装满，此时价值和为7+8+5+2×1=22。

可以验证，最优答案就是 22。

样例 2

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

限制

对于 30%的数据，n,V ≤ 20；

对于 100%的数据，n,V ≤ 5000。

保证数据中所有的整数均为正整数，且不超过 5000。时间：6 sec

空间：512 MB

提示

[经典的 01 背包和完全背包问题。]

代码

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

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

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

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

//f:动态规划用的数组，f[i]表示容量为i的背包的最大价值int f[N];

// n：物品个数

// V：背包的体积

// t：长度为n的数组，第i个元素若为0，表示物品i为单个物品；若为1，表示物品i为多个物品。

（i下标从0开始，下面同理）

// w：长度为n的数组，第i个元素表示第i个物品的价值

// v：长度为n的数组，第i个元素表示第i个物品的体积

// 返回值：最大价值之和

int getAnswer(int n, int V, vector<int> t, vector<int> w, vector<int> v) {

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

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

if (t[i] == 0)//01背包，倒序枚举

for (int j = V; j >= v[i]; --j)

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

else

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

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

return f[V];

}

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

int main() {

int n, V;

scanf("%d%d", &n, &V);

vector<int> T, W, _V;

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

int t, w, v;

scanf("%d%d%d", &t, &w, &v);

T.push_back(t);

W.push_back(w);

_V.push_back(v);

}

printf("%d\n", getAnswer(n, V, T, W, _V));

return 0;

}