首页 > 其他 > 详细

[hiho 07]完全背包

时间:2015-04-27 23:12:18      阅读:252      评论:0      收藏:0      [点我收藏+]

题目描述

状态 f[i, j] 表示已经决定前 i 种物品的选取,总 need 不超过 j;

状态转移方程 f[i, j] = max{f[i, j – need[i]] + val[i], f[i – 1, j]};

结果的状态表示为 f[n, m]。

注意状态方程与01背包的区别,这个区别反映了物品能取一个还是无穷个。

反映到代码上的区别就是内层循环的次序不同。

#include <iostream>
#include <algorithm>

using namespace std;

int f[100005];

int main() {
	int n, m;
	cin >> n >> m;

	int val, need;
	for (int i = 0; i < n; i++) {
		cin >> need >> val;
		for (int j = need; j <= m; j++) {
			f[j] = max(f[j], f[j - need] + val);
		}
	}
	cout << f[m] << endl;
	return 0;
}

REF:背包问题九讲

[hiho 07]完全背包

原文:http://www.cnblogs.com/xblade/p/4461585.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!