01背包问题

lexingsen

发布于 2022-02-25 08:35:47

1860

发布于 2022-02-25 08:35:47

文章被收录于专栏：乐行僧的博客

有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是vi，得到的价值是wi。求解将哪些物品装入背包可以使得价值之和最大。

二维数组的暴力解法，未涉及空间优化。 首先用子问题来定义状态，f[i][j]表示前i个物品放到容量为j的空间总价值最大。f[i][j]这个状态是由i-1推过来的，这里有两种考虑：第i中物品选择还是不选择，如果不选择f[i][j]==f[i-1][j]，如果选择f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i])。 max(f[i-1][j], f[i-1][j-v[i]]+w[i])的解释： 第i件物品选择，第i件物品占据的空间是v[i]，价值为w[i]。那么前i-1件物品所占据的空间为j-v[i]，价值为f[i-1][j-v[i]]。而f[i][j]是f[i-1][j]和f[i-1][j-v[i]]+w[i]其中较大的一个。

代码部分：

#include <iostream>
using namespace std;

const int maxn=1010;
int v[maxn], w[maxn];
int f[maxn][maxn];
int n, m; //分别表示物品总数为n 背包容量为m

int main() {
	cin >> n >> m;
	f[0][0] = 0;
	for (int i=1; i<=n; ++i) cin >> v[i] >> w[i];
	for (int i=1; i<=n; ++i) {
		for (int j=1; j<=m; ++j) {
			f[i][j] = f[i-1][j];
			if (j >= v[i]) {
				f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]);				
			}
		}
	}
	int res = 0;
	for (int i=0; i<=m; ++i) {
		res = max(res, f[n][i]);
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

max