题解：P1060 [NOIP2006 普及组] 开心的金明

solution

01 背包问题。

记

w_i

表示

v_i \times p_i

，即物品

i

占用的背包容量，设

f_{i, j}

表示前

i

个物品容量为

j

的背包的最大价值。

考虑转移。假设当前已经处理好了前

i-1

个物品的所有状态，那么对于第

i

个物品，当其不放入背包时，背包的剩余容量和总价值都不变，故这种情况的最大价值为

f_{i-1, j}

；当其放入背包时，背包的剩余容量会减小

w_i

，背包中物品的总价值会增大

v_i

，故这种情况的最大价值为

f_{i-1, j-w_i}+v_i

。

综上，转移是

f_{i, j}=\max(f_{i-1, j}, f_{i-1, j-w_i}+v_i)

。

由于对物品

i

影响的只有物品

i-1

，所以我们可以去掉一维，用

f_j

表示容量为

j

的背包的最大价值，转移是

f_j=\max(f_j, f_{j-w_i}+v_i)

。

最后我们注意枚举顺序，是从大到小的，否则则会出现一个物品多次放入背包的情况。

code

CPP

#include<bits/stdc++.h>
using namespace std;
int n, m, f[30001], v[30], p[30];
int main(){
	cin >> n >> m;
	for(int i=1; i<=m; i++)
		cin >> v[i] >> p[i],
		p[i]*=v[i];
	for(int i=1; i<=m; i++)
		for(int j=n; j>=v[i]; j--)
			f[j]=max(f[j], f[j-v[i]]+p[i]);
	cout << f[n];
	return 0;
}

题解：P1060 [NOIP2006 普及组] 开心的金明

文章操作

solution

code

相关推荐

评论

题解：P1060 [NOIP2006 普及组] 开心的金明