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

思路分析

这道题我们可以用背包来做（其实就是动态规划），首先他说总和是

v_{j1} \times w_{j1} + v_{j2} \times w_{j2} + \dots + v_{jk} \times w_{jk}

。

所以价格

v_i

就要转换为

v_i \times w_i

。

然后我们有两种方法去讨论第

i

种物品（即

dp[i][j]

）：

不取这件物品，就是只有前 $i-1$ 个物品的价值，转化为 $dp[i-1][j]$ 。
取这件物品，就会只有前 $i-1$ 个物品的价值，再去掉这个物品的容量，在后面再加上这个物品的价值，转化为 $dp[i-1][j-w[i]]+v[i]$ 。

对于每种物品，我们取这个物品每种情况的最大值就行了。

即动态转移方程

dp[i][j]=\max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])

。

最后我们用滚动数组来优化它就可以了，因为我们只需要

i-1

行的数据，至于上面

i-2,i-3,\dots,1

行的数据都不需要了。

代码解析

CPP

#include<bits/stdc++.h>
#define sjh0626s return
#define code 0
using namespace std;
int v[10100],w[10100],n,m,dp[30100];
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
		v[i]*=w[i];
	} 
	for(int i=1;i<=n;i++){
		for(int j=m;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		} 
	}
	cout<<dp[m];
	sjh0626s code;
}

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

文章操作

思路分析

代码解析

相关推荐

评论

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