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

洛谷P1060

本题是一个典型的 01 背包问题，可转化为每个物品的重量

vi

，价值为

vi×wi

，背包总容量为

N

。设

f[i][j]

表示当处理到第

i

件物品时，还有

j

的空间时所获的的价值（第

i

件物品可以选择取或者不取），可得状态转移方程：

f[i][j]=\min(f[i-1][j],f[i-1][j-vj]+vi\times wi)

再用滚动数组优化空间，时间复杂度为

O(N^2)

，空间复杂度为

O(N)

。

完结散花！

CPP

#include <bits/stdc++.h>
using namespace std;
int f[30001],v[26],w[26],n,m;
int main(){
  	cin>>n>>m;
  	for (int i=1;i<=m;i++){
      	cin>>v[i]>>w[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]]+v[i]*w[i]);
        }
    }
  	cout<<f[n]<<endl;
  	return 0;
}

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

文章操作

相关推荐

评论

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