题目描述

01背包问题

有n个重量和价值分别为\(w_i,v_i\)的物品。从这些物品中挑选出总重量不超过W的物品,求所有挑选方案中价值中总和的最大值。

限制条件

  • 1 <= n <= 100
  • 1 <= \(w_i,v_i\) <= 100
  • 1 <= W <= 10000

样例输入

n = 4
(w,v) = {(2,3) (1,2) (3,4) (2,2)}
W = 5

样例输出

7(选择0,1,3号物品)

暴力求解

# include <iostream>
# include <algorithm>
using namespace std;

int n, W;
const int MAX_N = 10000;
int w[MAX_N], v[MAX_N];

int rec(int i, int j)
{
    int res;
    if (i == n)
    {
        res = 0;//在递归中,这也就相当于是循环的终止条件了

    }
    else if (j < w[i])//无法挑选物品
    {
        res = rec(i + 1, j);//采用递归的方法,对下一个物品进行挑选
    }
    else//挑选和不挑选都尝试一下
    {
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);
        //对于挑选的情况,因为采用了递归的方式,j 最为各个物品之间的和,每次当然要减去
        //挑选出来的满足条件的上一个物品的重量,并且对于挑选出的满足条件的物品的价值进行相加
    }
    return res;
}

void solve()
{
    printf("%d\n", rec(0, W));//从第0件物品开始挑选
}

int main()
{
    cin >> n;
    cout << "输入每个物品的重量";
    for (int i = 0; i < n; i++)
    {
        cin >> w[i];
    }

    cout << "输入每个物品的价值";
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    cout << "输入不能超过的最大的重量";
    cin >> W;
    solve();

    return 0;
}

小结

  • 对于这一段代码,rec(i + 1, j - w[i]) + v[i] 尤其是对于这个可以挑选的这一段代码
    的解释,想了一一下,一开始是有一个j 作为标准,从第i个物品开始挑选重量 小于j的物品,如果挑选出
    来一个这样的物品了,那么再挑选下一个物品的时候就必须要把前一个物品的重量减去,然后以这个新的
    “重量”来挑选下一个物品,为什么要这样做呢,原因很简单,因为是要求挑选出的物品总重量必须不能超过
    W 的物品的重量。当然了,对于没有挑选出来的,根本也就不存在价值的可能。不用相加。
  • 对于递归其实在某种意义上市一种循环,只是循环的条件有所不同。

最新文章

  1. localStorage实现购物车数量单价和结算页面的实时同步
  2. 计蒜客 X的平方根
  3. Solr 删除数据的几种方式
  4. Java从入门到精通——基础篇之JSTL标签
  5. CRM窗体中只读的控件不会引发Update事件
  6. php图片上传
  7. mysql 锁表查询及其处理
  8. A. Liserious战队
  9. Poj 3771 hdu 3405
  10. 玩转Web之easyui(二)-----easy ui 异步加载生成树节点(Tree),点击树生成tab(选项卡)
  11. Windows store 验证你的 URL http:// 和 https:// ms-appx:/// ms-appdata:///local
  12. Unittest框架+ddt数据驱动+HTMLTestRunner+sendmail(自动发送测试报告)+git+Jenkins
  13. 使用XHProf查找PHP性能瓶颈
  14. Java 8 Optional 类
  15. 探索RequestBody报com.alibaba.fastjson.JSONObject cannot be cast to xxx
  16. 基于session做的权限控制
  17. [Go] 通过 17 个简短代码片段,切底弄懂 channel 基础
  18. python框架----&gt;pymysql的使用
  19. DataTable进行排序Asc升序,Desc降序
  20. oracle中查找锁定状态的用户

热门文章

  1. Element is not clickable at point error in chrome
  2. Android的47个小知识
  3. photoshop软件应用手记
  4. jmeter ---json几种读取方式,ArrayList循环读取
  5. java面向对象(三)之抽象类,接口,向上转型
  6. LVS之DR跨网段实战及高可用性
  7. JQuery的动态加载class无法实现点击时间的解决方案
  8. html加载和解析流程
  9. grunt之watch续
  10. 201521123084 《Java程序设计》第7周学习总结