Hiho Coder 1038 01背包(模板)

Ch_Zaqdt

发布于 2019-01-10 11:15:31

3530

发布于 2019-01-10 11:15:31

文章被收录于专栏：Zaqdt_ACM

01背包的原型就是有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是Ci，得到的价值是Wi，求将哪些物品装入背包可使获得的价值总和最大。而这道题的题意也就是这个意思，01背包的特点就是每种物品仅有一件，可以选择放或者不放。

下面是01背包的核心代码：

for(int i = 0; i < n; i++){
  for(int j = V; j >= c[i]; j--){
    dp[j] = max(dp[j] , dp[j-c[i]] + w[i]);
  }
}

这个核心代码是由二维的状态转移方程优化来的(至于什么是状态转移方程捉着想知道怎么优化的自己去查一下吧~~)，懂了这个核心代码后01背包的问题就不是问题了。

AC代码：

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 200005;
int dp[MAXN];
int val[MAXN];           // 价值
int c[MAXN];             // 体积
int n,m;
int main()
{
  while(cin>>n>>m){
    for(int i = 0;i<n;i++){
      cin>>c[i]>>val[i];
    }
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++){
      for(int j=m;j>=c[i];j--){
        dp[j] = max(dp[j],dp[j-c[i]]+val[i]);
      }
    }
    cout<<dp[m]<<endl;
  }
  return 0;
}
/*
  [来源] hiho Coder 1038
  [题目]
     01背包
  [大意]
     01背包模板题
  [输入]
  5 1000
  144 990
  487 436
  210 673
  567 58
  1056 897
  [输出]
  2099
*/

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

原始发表：2018年02月06日，如有侵权请联系 cloudcommunity@tencent.com 删除

优化