关键词：
背包问题大部分是这样的：有一个容量为V的背包和一些物品。这些物品有两个属性，体积ｗ和价值ｖ，每种物品只有一个。
要求用这个背包装下价值尽可能多的物品，求其最大价值。因为在最优解中，每个物品都有两种可能的情况，即在背包中存在
或者不存在（背包中有0个或者1个该物品），因而被称为0-1背包问题。
采药
题目描述
辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。 为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。 医师把他带到个到处都是草药的山洞里对他说： “孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。 我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？
输入描述:
输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出描述:
可能有多组测试数据，对于每组数据，
输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
示例1
输出
3
1 #include <stdio.h>
2 #include <limits.h>
3
4 int max( int a,int b)
5 {
6 return a > b ? a:b;
7 }
8
9 struct E
10 {
11 int w; //物品时间
12 int v; //物品价值
13 } list[101];
14 int dp[1001];
15
16 int main()
17 {
18 int s,n;
19 int i,j;
20 while( scanf("%d%d",&s,&n)!=EOF)
21 {
22 for( i=1; i<=n; i++)
23 scanf("%d%d",&list[i].w,&list[i].v);
24 for(i=0; i<=s; i++ )
25 dp[i]=0;
26 for( i=1; i<=n; i++)
27 {
28 for( j=s; j>=list[i].w; j--) //倒序更新
29 dp[j] = max( dp[j],dp[j-list[i].w]+list[i].v); //状态转移方程
30 }
31 printf("%d
",dp[s]);
32 }
33
34 return 0;
35 }
这里采用倒序更新是为了保证更新dp[j] 时，dp[ j-list[i].w ]的状态尚未因此次更新而发生改变。
动态规划之0-1背包问题(代码片段)
问题描述：给定n种物品，1个背包，背包容量为c,每个物品i的价值为vi，重量为wi，如何选择装入物品能使背包的总价值最大？注意：1）对于每个物品来说，只有两种选择，要么装，要么不装！ 2）不能... 查看详情
c++算法主题系列之集结0-1背包问题的所有求解方案(代码片段)
1.前言背包问题是类型问题，通过对这一类型问题的理解和掌握，从而可以归纳出求解此类问题的思路和模板。背包问题的分类有：0-1背包问题，也称为不可分割背包问题。无限背包问题。判定性背包问题.带附属关系的背包问题... 查看详情
动态规划之0-1背包问题
...他数了数，一共有n个。但他身上能装宝石的就只有一个背包，背包的容量为C。这哥们把n个宝石排成一排并编上号：0,1,2,…,n-1。第i个宝石对应的体积和价值分别为V[i]和W[i]。排好后这哥们开始思考：背包总共也就只能装下体 查看详情
动态规划算法之0-1背包问题
...求解下一个子问题时会用到上一个子问题的答案。比如01背包问题：假如有1个背包，背包容量是10，有5个物品，编号为1，2，3，4，5，他们都有各自的重量和价格。要求在不超过背包容量 查看详情
动态规划算法之0-1背包问题
...求解下一个子问题时会用到上一个子问题的答案。比如01背包问题：假如有1个背包，背包容量是10，有5个物品，编号为1，2，3，4，5，他们都有各自的重量和价格。要求在不超过背包容量 查看详情
动态规划之背包问题(代码片段)
本文有视频版：0-1背包问题详解后台天天有人问背包问题，这个问题其实不难啊，如果我们号动态规划系列的十几篇文章你都看过，借助框架，遇到背包问题可以说是手到擒来好吧。无非就是状态+选择... 查看详情
算法分析之背包问题
题意给定一个载重量为M的背包，考虑n个物品，其中第i个物品的重量wi，价值vi（1≤i≤n），要求把物品装满背包，且使背包内的物品价值最大。有两类背包问题（根据物品是否可以分割），如果物品不可以分割，称为0-1背包问... 查看详情
背包问题：0-1背包完全背包和多重背包
背包问题泛指以下这一种问题：给定一组有固定价值和固定重量的物品，以及一个已知最大承重量的背包，求在不超过背包最大承重量的前提下，能放进背包里面的物品的最大总价值。这一类问题是典型的使用动态规划解决的问... 查看详情
转载动态规划之背包问题
...他数了数，一共有n个。但他身上能装宝石的就只有一个背包，背包的容量为C。这哥们把n个宝石排成一排并编上号：0,1,2,…,n-1。第i个宝石对应的体积和价值分别为V[i]和W[i]。排好后这哥们开始思考：背包总共也就只能装下体积... 查看详情
动态规划之背包问题(代码片段)
后台天天有人问背包问题，这个问题其实不难啊，如果我们号动态规划系列的十几篇文章你都看过，借助框架，遇到背包问题可以说是手到擒来好吧。无非就是状态+选择，也没啥特别之处嘛。今天就来说一下背包问题吧，就讨... 查看详情
0-1背包问题——四种解法解题(代码片段)
...分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。注：0/1背包问题：给定种物品和一个容量为的背包，物品的重量是，其价值为，背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最大... 查看详情
10.动态规划——0-1背包问题
...子集和问题》中，谈到了什么是子集和问题，以及实现。背包问题实际也是子集和问题的一种，不过背包问题不是“判断问题”而是一个“最优问题”。而背包问题实际上又分为“0-1背包”，“完全背包&rdqu... 查看详情
1085背包问题（0-1背包模板题）
1085背包问题（0-1背包模板题）（51NOD基础题）基准时间限制：1秒空间限制：131072KB分值:0难度：基础题 在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn... 查看详情
0-1背包问题
0-1背包问题0-1背包问题描写叙述 有一个窃贼在偷窃一家商店时发现有n件物品。第i件物品价值为vi元，重量为wi，如果vi和wi都为整数。他希望带走的东西越值钱越好，但他的背包中之多仅仅能装下W磅的东西，W为一整数。他应... 查看详情
0-1背包问题
问题： 给定n种物品和一背包。物品i的重量是wi，其价值是vi，背包的容量为c。 对于一件物品，只有装或者不装，因此该问题称为0-1背包问题。 问如何选择装入背包中的物品，使得装入背包中的物品总价值最大。分... 查看详情
背包0-1背包与完全背包一维数组实现(代码片段)
背包问题很经典了，《背包问题九讲》讲的非常详细，建议看一看。在这里，我想给出0-1背包和完全背包压缩空间后的实现，即只要一维数组。0-1背包，与完全背包仅仅只是内循环的次序不同，故而代码基本相同。希望可以帮的... 查看详情
动态规划之背包问题(代码片段)
本文有视频版：0-1背包问题详解后台天天有人问背包问题，这个问题其实不难啊，如果我们号动态规划系列的十几篇文章你都看过，借助框架，遇到背包问题可以说是手到擒来好吧。无非就是状态+选择... 查看详情
优化算法系列-模拟退火算法——0-1背包问题(代码片段)
优化算法系列之模拟退火算法（1）——0-1背包问题1问题描述有一个窃贼在偷窃一家商店时发现有N件商品：第i件物品价值vi元，重wi磅，其中vi、wi都是整数。他希望带走的东西越值钱越好，但他的背包小，最多只能装下W磅的东... 查看详情