目录
一、背包简介
背包其实就是动态规划，可以推出方程，但因为其比较常见，所以单独挑出来。
二、背包种类
1.01背包
因为他只有选和不选两种，所以被比作01；
1.二维
问题描述：
给定 n 件物品，物品的重量为 weight，对应的价值为 value。现挑选物品放入背包中，假定背包能承受的最大重量 W 为 m，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？令 dp[i][w] 表示前 i 件物品放入容量为 w 的背包中可获得的最大价值。为了方便处理，我们约定下标从 1 开始。
对于编号为 i 的物品：
- 如果选择它，那么，当前背包的最大价值等于” i 号物品的价值“ 加上 ”减去 i 号物品占用的空间后剩余的背包空间所能存放的最大价值“，即dp[i][k] = value[i] + dp[i-1][k-weight[i]]；
- 如果不选择它，那么，当前背包的价值就等于前 i-1 个物品存放在背包中的最大价值，即 dp[i][k] = dp[i-1][k]
转移方程：
dp(i,j) = max(dp(i-1,j),dp(i-1,j-w(i))+v(i));代码实现如下：
#include "iostream"
#include "iomanip"
using namespace std;
//最优解状态空间
int dp[100][100];
int value[100];
int weight[100];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>weight[i]>>value[i];
//递推求解dp状态
for (int i = 1; i <=n ; ++i) {//3个物品
for (int j = 1; j <=m ; ++j) {//背包空间
//不选i物品，最大与dp[i-1][j]相等
int without = dp[i-1][j];
//选i物品：
// 首先必须空间能放得下i物品
// 其次选择该物品的价值：当前物品的价值 + 剩余空间的最大价值
int with = weight[i]<=j?dp[i-1][j-weight[i]]+value[i]:0;
dp[i][j] = max(without,with);
}
}
//打印dp状态
for (int i = 1; i <=n ; ++i) {
for (int j = 1; j <=m ; ++j) {
cout<<setw(m)<<dp[i][j]<<" ";
}
cout<<endl;
}
}2.一维
我们之前分析出01背包的状态转移方程：
dp[i][k] = max(value[i] + dp[i-1][k-weight[i]], dp[i-1][k])观察上面的代码，会发现，当更新dp[i][k]时，只与dp[i-1][..]有关，也就是说，我们没有必要使用O(n*W)的空间，而是只使用O(W)的空间即可。
for (int i = 1; i <=n ; ++i) {
for (int k = c; k >=1 ; k--) {
//选
int value_with = (k - weight[i] >= 0) ? (dp[k - weight[i]] + value[i]) : 0;
//不选
int value_without = dp[k];
dp[k] = max(value_with,value_without);
}
}这里的状态转移方程变成了：
dp[k] = max(value[i]+dp[k-weight[i]], dp[k])2.完全背包
问题描述
有n种物品，每种物品的单件重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品都有无穷件。对于01背包问题，每种物品只有两种选择：选和不选，我们推导的转移方程如下：
dp[k] = max(value[i]+dp[k-weight[i]], dp[k])完全背包问题中，每个物品有无限件，也就是从每种物品的角度考虑，与它相关的策略并非选或者不选两种。而是：选0件、选1件、选2件…等等多种策略。
我们借鉴01背包问题的思路，将每种选择策略的结果都计算出来，然后取所有策略状态的最大值，转移方程如下：
令dp[i][j]表示前i种物品放入容量为j的背包的最大价值：
dp[i][j] = max{dp[i-1][j-k*weight[i]]+k*value[i]|0<=k*value[i]<=j}核心代码：
//完全背包：递推求解dp状态
for (int i = 1; i <=n ; ++i) {//物品
for (int j = 1; j <=c ; ++j) {//背包空间
//这里需要计算所有策略，对应01背包问题，这里只需要计算选和不选两种策略
for (int k = 0; k*weight[i] <= j ; ++k) {
dp[i][j] = max(dp[i][j],dp[i-1][j-k*weight[i]]+k*value[i]);
}
}
}三、例题
1.金明的预算方案
由题目我们知道，一个主件最多有两个附件，且必须先买主件，所以：
1.只选主件，不选附件：dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
2.选主件和第一个附件：dp[j]=max(dp[j],dp[j-w[i]-w1[i][1]]+v[i]+v1[i][1]);
3.选主件和第二个附件：dp[j]=max(dp[j],dp[j-w[i]-w1[i][2]]+v[i]+v1[i][2]);
4.选主件和所有附件：dp[j]=max(dp[j],dp[j-w[i]-w1[i][1]-w1[i][2]]+v[i]+v1[i][1]+v1[i][2]);
2.机器分配
总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。
问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。
分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。
输入格式:
输入包含一组数据：第一行有两个数，第一个数是分公司数N，第二个数是设备台数M。
接下来是一个N*M的矩阵，表明了第 I个公司分配 J台机器的盈利。
输出格式:
输出第一行为最大盈利值；
接下来有n行，分别为各分公司分配的机器数。
限制:
空间限制：128MByte
时间限制：1秒
样例:
输入： 3 3
30 40 50
20 30 50
20 25 30
输出：
70
1 1
2 1
3 1
提示:
要求答案的字典序最小
#include<iostream>
using namespace std;
int n,dp[20][20],m,v[20][20],sum[20][20];
void print(int i,int j){
if(i==0) return;
print(i-1,j-sum[i][j]);
cout<<i<<" "<<sum[i][j]<<endl;
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
cin>>v[i][j];
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
for(int k=0; k<=j; k++)
if(j>=k)
if(dp[i][j]<dp[i-1][j-k]+v[i][k]) {
dp[i][j]=dp[i-1][j-k]+v[i][k];
sum[i][j]=k;
}
cout<<dp[n][m]<<endl;
print(n,m);
return 0;
}