题目链接:poj 3624

这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。
            用子问题定义状态:即F [i, v]表示前i件物品恰放入一个容量为v 的背包可以
            获得的最大价值。则其状态转移方程便是:
            F [i, v] = max{F [i − 1, v], F [i − 1, v − Ci ] + Wi }
            这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生
            出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v 的背包

中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化
            为一个只和前i − 1件物品相关的问题。如果不放第i件物品,那么问题就转化
            为“前i − 1件物品放入容量为v 的背包中”,价值为F [i − 1, v];如果放第i件物
            品,那么问题就转化为“前i − 1件物品放入剩下的容量为v − Ci 的背包中”,
            此时能获得的最大价值就是F [i − 1, v − Ci ]再加上通过放入第i件物品获得的价
            值 Wi 。
            伪代码如下:
            F [0, 0..V ] = 0
            for i = 1 to N
                  for v = Ci to V
                        F [i, v] = max{F [i − 1, v], F [i − 1, v − Ci ] + Wi }

以上方法的时间和空间复杂度均为O(V N ),其中时间复杂度应该已经不能
            再优化了,但空间复杂度却可以优化到O(V )。
            先考虑上面讲的基本思路如何实现,肯定是有一个主循环i = 1..N ,每次
            算出来二维数组F [i, 0..V ]的所有值。那么,如果只用一个数组F [0..V ],能不
            能保证第i次循环结束后F [v]中表示的就是我们定义的状态F [i, v]呢?F [i, v]是
            由F [i − 1, v]和F [i − 1, v − Ci ]两个子问题递推而来,能否保证在推F [i, v]时(也
            即在第i次主循环中推F [v]时)能够取用F [i − 1, v]和F [i − 1, v − Ci ]的值呢?事
            实上,这要求在每次主循环中我们以v = V..0的递减顺序计算F [v],这样才能保
            证推F [v]时F [v − Ci ]保存的是状态F [i − 1, v − Ci] 的值。伪代码如下:
            F [0..V ] = 0
            for i = 1 to N
                  for v = V to Ci
                       F [v] = max{F [v], F [v − Ci ] + Wi }
            其中的F [v] = max{F [v], F [v − Ci ] + Wi }一句,恰就对应于我们原来的转移方
            程,因为现在的F [v − Ci ]就相当于原来的F [i − 1, v − Ci ]。如果将v 的循环顺序
            从上面的逆序改成顺序的话,那么则成了F [i, v]由F [i, v − Ci ]推导得到,与本题
            意不符。
            代码:

#include<stdio.h>
#include<iostream>
#include<string.h>
#define N 3405
using namespace std;
int bag[12900];
int w[N],d[N];
int main(void)
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>w[i]>>d[i];
memset(bag,0,sizeof(bag));
for(int i=1;i<=n;i++)
for(int k=m;k>=w[i];k--)
{
if(bag[k-w[i]] + d[i] > bag[k])
bag[k] = bag[k - w[i]] + d[i];
}
cout<<bag[m]<<endl;
return 0;
}

最新文章

  1. 移动前端开发-单页应用(spa)模型
  2. 怎样使用My97日期控件
  3. 我的android学习经历32
  4. zoj3416 Balanced Number
  5. Ambari源代码分析之总览
  6. 《Genesis-3D开源游戏引擎-FQA常见问题解答》2014年01月10号版本
  7. CentOS7 安装LAMP环境
  8. MPlayer
  9. 使用国内镜像通过pip安装python的一些包 Cannot fetch index base URL http://pypi.python.org/simple/
  10. React Native专题
  11. memcmp()直接比较两个数组的大小
  12. 位运算及在java中的应用整理
  13. JJG 623-2005 电阻应变仪计量检定规程
  14. Spring 配置文件XML -- &lt;beans&gt;中属性概述
  15. KMP Algorithm 字符串匹配算法KMP小结
  16. linux 杀死进程
  17. ReactiveCocoa基础
  18. Android学习之基础知识四-Activity活动4讲(Intent传递数据)
  19. ng-深度学习-课程笔记-11: 卷积神经网络(Week1)
  20. appium+python自动化98-非select弹出选择框定位解决

热门文章

  1. Android Material Design调色板
  2. CMD Create Database &amp; Table
  3. 鼠标经过图片时变换的两种方法--css+div及javascript应用
  4. zend framework安装中出现的问题与总结
  5. mysql错误提示不是英语的解决办法
  6. IP地址、子网掩码和地址分类
  7. Arduino当avr开发板
  8. 全数字锁相环(DPLL)的原理简介以及verilog设计代码
  9. Oracle EBS-SQL (BOM-1):检查供应类型错误.sql
  10. IE添加信任站点并设置允许ActiveX控件的VBS脚本