蒟蒻谈一下自己对于背包问题的理解

• 简介背包问题
• 0/1背包及其优化
• 完全背包及其优化
• 多重背包及其优化
• emmmmmmm，后面那几种背包不太会，就不讲了（滑稽）

一、背包问题：

引用百度百科一句话

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkel和Hellman提出的。
背包问题已经研究了一个多世纪，早期的作品可追溯到1897年 [1] 数学家托比亚斯·丹齐格（Tobias Dantzig，1884-1956）的早期作品 [2] ，并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。

（好吧其实写不写都是无所谓的，主要是懒得自己介绍了，这些东西知道就好了）
其实所有背包问题都是很相似的，中心特点就是放各种东西
1、能放几个？
2、怎么放？

二、0/1背包及其优化

（1）、0/1背包基础做法：

题目描述
一个旅行者有一个最多能用 m 公斤的背包，现在有 n 件物品，它们的重量分别是 W1 ，W2 ，… , Wn ,它们的价值分别为 C1，C2 ，… ，Cn 。若每种物品只有一件求旅行者能获得最大总价值。
输入格式
第 1 行：两个整数，M（背包容量，M≤200）和 N（物品数量，N≤30）。
第 2..N+1 行：每行二个整数 Wi，Ci，表示每个物品的重量和价值。
输出格式
仅一行，一个数，表示最大总价值。
样例数据 1
输入
10 4
2 1
3 3
4 5
7 9
输出
12

基础的0/1背包的板子题，主要特点就是只能放一个。
对于每一件物品来说，只有两个选择：放？还是不放？
不放的话总价值就等于原价值，而放了的话当前背包的价值就等于当前背包已占有容量减去该物品占有容量的价值加上该物品的价值，分析过程
如果一个个物品从左往右递推的话
我们可以用数组dp [ i ] [ j ]表示推到第 i 个物品时，占据的空间为 j 时的最大价值
那么我们就可以列出方程式

for(int i=1;i<=n;i++)
{for(int j=1;j<=m;j++){if(w[i]<=j) dp[i][j]=max(dp[i-1][j-w[i]]+c[i],dp[i-1][j]);else dp[i][j]=dp[i-1][j];}
}

可能还有个不算问题的nc问题（只是备注一下而已，Rbl的问题）
枚举空间时为什么是从1到m依次加1
其实如果有那个能耐，可以直接把1~m之间的所有能凑出来的总价值罗列出来从小到大排个序，但反而得不偿失，谁要是真的无聊可以这样做。
（2）、0/1背包的优化：
时间复杂度 O ( m n ) 已经到极限了，基本上是无法优化的，当然我不知道上面那个算不算也许可能应该大概能优化时间，我们主要考虑优化空间S（m n ) 成S( m )；
重点理解！后面完全背包也有很大用！
这样写

for(int i=1;i<=n;i++)
{for(int j=m;j>=1;j--){if(w[i]<=j)dp[j]=max(dp[j],dp[j-w[i]]+c[i]);}
}
cout<

if(w[i]<=j)
dp[j]=max（dp[j],dp[j-w[i]]+c[i])

if（w[i]<=j) 
dp[i][j]=max(dp[i-1][j-w[i]]+c[i],dp[i-1][j]);
else dp[i][j]=dp[i-1][j] ;

if（w[i]<=j) 
dp[i][j]=max(dp[i][j-w[i]]+c[i],dp[i-1][j]);
else dp[i][j]=dp[i-1][j] ;

#include
#include
using namespace std;
int a[205],s[205],n,m,dp[205];
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>a[i]>>s[i];
for(int i=1;i<=n;i++)
{for(int v=1;v<=m;v++){if(v>=a[i])dp[v]=max(dp[v],dp[v-a[i]]+s[i]);}
}
cout<

for(int i=1;i<=n;i++)
{for(int j=1;j<=m;j++){if(w[i]<=j)dp[j]=max(dp[j],dp[j-w[i]]+c[i]);}
}
cout<