一、01背包

1.01背包引入

是背包中最简单的问题。
01背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。在01背包问题中，因为每种物品只有一个，对于每个问题只需要考虑选与不选两种情况。如果不选将其放入背包中，则不需要处理。如果选择将其放入背包中，由于不清楚之前收入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。

2.01背包例题

例题1：现有四个物品，小偷背包总容量为8，怎么可以偷得价值最多的物品？如：物品编号：1 2 3 4物品重量：2 3 4 5物品价值：3 4 5 8记f(k,w）：当背包容量为w，现有k件物品可以偷，所能偷到最大价值

 #include<cstdio>  #include <iostream>  #include<cstdlib>  #include<algorithm>  #include <cstring>  using namespace std;  int f[5][9] = {0};  int w[5] ={0,2,3,4,5};  int v[5] ={0,3,4,5,8};  int main(){  int i,j;  memset(f,0,sizeof(f));  for(int i = 1; i < 5; i++){  for(int j = 1; j < 9; j++){  if(w[i] > j){  f[i][j] = f[i - 1][j];  }else{  f[i][j] = max(f[i - 1][j],f[i - 1][j - w[i]] + v[i]);  }  }  }  for(int i = 0; i < 5; i++){  for(int j = 0; j < 9; j++){  cout <<"f["<< i << "]" <<"[" << j<<"]= " << f[i][j] << endl;  }  }  } 

3.01背包空间优化

滚动数组：根据后无效性原则，下一状态只与上一个状态有关，可以压缩成一维数组。每运行一遍就让让dp数组刷新一遍；注意求新的dp数组时必须倒着，背包剩余容量要从容量最大值开始，不然物体的小容量会被这个物品的小容量值覆盖。比如dp[8] = max(dp[8],dp[4] + 6)此时这一层的dp[4]还未更新还为上一层的，直接使用即可，如果正着推，此时dp[4]已经覆盖为这一层的，无法正确求出后面的；

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

输入格式
第一行有 22 个整数 TT（1 \le T \le 10001≤T≤1000）和 MM（1 \le M \le 1001≤M≤100），用一个空格隔开，TT 代表总共能够用来采药的时间，MM 代表山洞里的草药的数目。

接下来的 MM 行每行包括两个在 11 到 100100 之间（包括 11 和 100100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式
输出在规定的时间内可以采到的草药的最大总价值。

如果你是辰辰，你能完成这个任务吗？
1).未进行压缩的动态规划

#include<iostream>
#include<algorithm>
using namespace std;
const int n = 10001;
int dp[n][n];
int t[n];
int v[n];
int main(){int T,m,i,j;cin >> T >> m;for(i = 1; i <= m; i++){cin >> t[i] >> v[i];}for(i = 1; i <= m; i++){for(j = 1; j <= T; j++){if(t[i] > j){dp[i][j] = dp[i - 1][j];}else{dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - t[i]] + v[i]);}} }cout << dp[m][T];
} 

2).压缩后的动态规划（利用滚动数组）

#include<bits/stdc++.h>
using namespace std;
const int n = 10001;
int dp[n];
int t[n];
int v[n];
int main(){int T,m;cin >> T >>m;for(int i = 1; i <= m; i++){cin >> t[i] >> v[i];}for(int i = 1; i <= m; i++){for(int j = T; j >= 1; j--){  //递推j必须倒着循环，否则会被覆盖if(j >= t[i]){dp[j] = max(dp[j],dp[j - t[i]] + v[i]);}}}cout << dp[T];
}

例题2：许多前年，在泰迪的家乡，有一个人被称为古收藏家，他喜欢收集不同的骨头。这个人有一个大袋子（袋子的体积为V），以及很多收集的骨头，很明显，不同的骨头有不同的价值和不同的体积，现考虑到每个骨头的价值以及他的袋子，请计算出这个人能收集到骨头的最大总价值？

输入：
开始输入一个数t,表示有t组测试数据。每个测试数据开始输入两个数n和v，表示骨头的总数和袋子的体积。接下一行输入n个数，表示n个骨头的价值。最后一行输入n个数，表示n个骨头的体积。
输出：
每个测试数据输出一个数，表示最大的价值。
样例输入：
1
5 10
1 2 3 4 5
5 4 3 2 1
样例输出：14

#include <iostream>  
#include <cstring>  
#include <cmath>  
using namespace std;  
const int n = 1000;  
int dp[n][n];  
int val[n];  
int vo[n];  
int main()  
{  int t;  cin >> t;  while (t--)  {  int n, v;  memset(dp, 0, sizeof(dp));  cin >> n >> v;  for (int i = 1; i <= n; i++)  {  cin >> val[i];  }  for (int i = 1; i <= n; i++)  {  cin >> vo[i];  }  for (int i = 1; i <= n; i++)  {  for (int j = 0; j <= v; j++)  {  if (vo[i] > j)  {  dp[i][j] = dp[i - 1][j]; //放不下  }  else  {  dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vo[i]] + val[i]); //将第i件物品放入背包之后的总价值  }  }  }  cout << dp[n][v] << endl;  }  }  

二、完全背包

1.完全背包引入

完全背包的问题是：有N种物品和一个容量为V的背包。第i种物品有若干见可用，每件费用是c[i]，价值是w[i].求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值量最大。完全背包和01背包问题很像，不同的是完全背包中的物品每件有若干件，而01背包中只有一件。

2.完全背包使用

设有n种物品，每种物品有一个重量和一个价值但是每种物品的数量是无限的，同时有一个背包，最大容量为M，今从n种物品中选取若干件（同一种物品可以多次选择），使其重量的和小于等于M，而价值的和为最大。

输入：
第一行：两个整数，M（背包容量，M<=200）和N（物品数量,N<=30);
第2,…N+1行：每行两个整数，Wi，Ci表示每个物品的数量和价值
输出：
仅一行，一个数，表示最大总价值。
样例输入：
10 4
2 1
3 3
4 5
7 9
样例输出：
max = 12
法一：（朴素方法）

每个物品可以取0，1，2....直到背包装不下（当前背包价值/w[i])
#include<iostream>  
#include<algorithm>  
#include<cmath>  
using namespace std;  
const int n = 10001;  
int c[n];  
int w[n];  
int dp[n];  
int main() {  int m,n;  cin >> m >> n;   for(int i = 1; i <= n; i++) {  cin >> w[i] >> c[i];  }  for(int i = 1; i <= n; i++){  for(int j = m; j >= 1; j--){  for(int k = 0; k <= j / w[i]; k++){  dp[j] = max(dp[j],dp[j - k*w[i]] + k*c[i]);  }  }  }  cout << "max = " << dp[m];  
}  

法二、终极算法：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int n = 10001;
int c[n];
int w[n];
int dp[n];
int main() {int m,n;cin >> m >> n;for(int i = 1; i <= n; i++) {cin >> w[i] >> c[i];}for(int i = 1; i <= n; i++) {
//		for(int j = 0; j <= m; j++) { //正向推 
//			if(j >= w[i]) {
//				dp[j] =max(dp[j],dp[j - w[i]] + c[i]);
//			}
//		}for(int j = w[i]; j <= m; j++){dp[j] =max(dp[j],dp[j - w[i]] + c[i]); //直接从能放的下的时候开始推 } }cout << "max = " << dp[m];
}

3.完全背包与01背包的区别

例题：请帮一个女生制定一个食谱，能使她吃的开心的同时，不会制造太多的卡路里。当然为了方便制作食谱，她给你了每日食物清单，上面描述了她想吃的每种食物能给她带来的幸福程度，以及会增加的卡路里量。

输入：
输入包含多组测试用例。每组数据以一个整数n开始，表示每天的食物清单有n种食物。接下来n行，每行两个整数a和b，其中a表示这种食物可以带给她的幸福值（数值越大越幸福），b表示会增加的卡路里量。最后是一个整数m，表示一天增加的卡路里不能超过m。
输出：
对每份清单，输出一个整数，即满足卡路里的同时，她可获得的最大幸福值。

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e6 + 10;
int n;
int c[maxn];
int f[maxn];
int dp[maxn];
int main(){while(cin >> n){for(int i = 1; i <= n; i++){cin >> f[i] >>c[i];}int m;cin >> m;for(int i = 1; i <= n; i++){for(int j = c[i]; j <= m; j++){dp[j] = max(dp[j],dp[j - c[i]] + f[i]);}}cout << dp[m] << endl; }
}