背包问题
参考资料：https://oi-wiki.org/dp/knapsack/ 《背包九讲》 《代码随想录》
前人之述备矣，作为后来者，主要是学习和记录一些自己花时间才明白的地方。
空间复杂度优化问题
0-1背包的dp解决可以从二维数组降维为一维数组，原理在于 最大价值【容量i，前j个物品】=max（最大价值【容量i-第j个物体占有空间，前j-1个物品】+ 第j个物品价值，最大价值【容量i，前j-1个物品】） 可以用一个数组记录某个容量时，允许放所有物体时最大的情况。 最大价值【容量i】=max（最大价值【容量i】，最大价值【容量i-第j个物品占有空间】+ 第j个物品价值） 这个做法需要从后往前遍历填表，一开始不太好思维上绕过来。
问题在于，用于更新的数据，是否在该物品的轮次已经被修改过： 
回到二维表格，我们可以看到，前j个物体的情况，数据来源都是前j-1个物体时的数据，在二维表格表示的情况下逆序填表也是正确的： 
因此可以从0-1背包自然过渡到完全背包的简洁写法，允许使用在该物体轮次已经被修改过的数据，就可以让一个物体被使用多次，从而达到完全背包的效果。 多重背包允许一个物体取有限次，那么新增物体，转化成01背包就可以。 通过对每个新增物体填表遍历顺序的改变（是否使用该物体轮次已被修改过的数据），就可以控制01和完全的物体。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
/*
0-1背包
*/
void Bag01(vector<int> weight ,vector<int> value ,int bagWeight) {
// 初始化
vector<int> dp(bagWeight + 1, 0);
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[bagWeight] << endl;
}
/*
完全背包
*/
void BagWhole(vector<int> weight ,vector<int> value ,int bagWeight) {
// 初始化
vector<int> dp(bagWeight + 1, 0);
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[bagWeight] << endl;
}
/*
多重背包，每个物品可以取有限次，可以转换为01背包解决
*/
void BagMulti(vector<int> weight ,vector<int> value ,int bagWeight,vector<int> times) {
//转化成01背包
for(int i=0;i<times.size();i++){
for(int j=0;j<times[i];j++){
weight.push_back(weight[i]);
value.push_back(value[i]);
}
}
// 初始化
vector<int> dp(bagWeight + 1, 0);
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[bagWeight] << endl;
}
/*
混合，物体有不限量，限量（取为1就是01）
*/
void BagMix(vector<int> weight ,vector<int> value ,int bagWeight,vector<int> times) {
//假设times值为-1说明是不限量
//转化成限量部分转化为01背包
for(int i=0;i<times.size();i++){
if(times[i]==-1) continue;
for(int j=0;j<times[i];j++){
weight.push_back(weight[i]);
value.push_back(value[i]);
times.push_back(1);
}
}
// 初始化
vector<int> dp(bagWeight + 1, -INT16_MAX);
dp[0]=0;
for(int i = 0; i < weight.size(); i++) { // 遍历物品
if(times[i]==-1){//不限量
for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}else{//限量
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
}
cout << dp[bagWeight] << endl;
}
恰好装满 && 记录过程
使用一个状态值记录是否能够恰好装满，例如使用负值记录不能恰好装满的情况。初始化时，容量为0的时候记录为0，其他情况都应该为负值，这样才可以用到容量为0时的状态去更新。更新时事实上细分四种情况。
记录过程是考察能否完全理解背包的每一步，明白完整写法是什么。简洁的min，max事实上掩盖了对情况的分类，需要记录过程的话一般需要写完整。
示例代码：
//以下是变式技巧
/*
0-1背包，要求恰好装满
*/
void Bag01Full(vector<int> weight ,vector<int> value ,int bagWeight) {
// 初始化,第一个设为0，后面为-
vector<int> dp(bagWeight + 1, -INT16_MAX);
dp[0]=0;
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);//这个其实是简洁写法，这一句的作用并非不更新，而是更新之后如果不成功应该还为负值（因为初始化了-INT_MAX）
//完整应该判读上一个物品这个容量dp[i-1][j]是否恰好装入和放入这个物体之前dp[i][j-v[i-1]]是否恰好装入的情况下，详见下面的BagWhole_Full_Min_Record()
}
}
cout << dp[bagWeight] << endl;
}
//01背包，并记录加入的物体
void bag01_record() {
vector<int> bag={0,7,4,3,3,1};
int n=5;
int maxWeight=9;
vector<int> dp(maxWeight+1,0);
vector<vector<int>> record(maxWeight+1,vector<int>());
//记忆点：容量从0表示到最大值
//物品从0遍历或从1遍历完整
//填表和打印时都要注意for循环是否遍历正确了
for(int i=1;i<=n;i++){
for(int j=maxWeight;j>=bag[i];j--){
if(dp[j-bag[i]]+bag[i]>dp[j]){
dp[j]=dp[j-bag[i]]+bag[i];
//更新某个容量的记录，应该是重新写这个记录，然后加入这个新物体
record[j]=record[j-bag[i]];
record[j].emplace_back(i);
}
}
}
for(int i=0;i<=maxWeight;i++){
cout<<i<<":"<<dp[i]<<endl;
for(int j=0;j<record[i].size();j++){
cout<<record[i][j]<<" ";
}
cout<<endl;
cout<<endl;
}
}
//找完全背包情况下，恰好装满背包最少使用数量，这里用的是没有空间复杂度优化的写法，方便理解
void BagWhole_Full_Min_Record() {
int n,m;
cin>>n>>m;
vector<int> v;
int temp;
for(int i=0;i<n;i++){
cin>>temp;
v.push_back(temp);
}
//记录放入的物品序号,行为容量，记录每个容量对应的物体序号
vector<vector<int>> record(m+1,vector<int>());
//恰好背包初始化，第一位为0，后续所有为负值
//填表时如果是负值就不填，取大值
//dp是记录放入物品数量
vector<vector<int>> dp(n+1,vector<int>(m+1,-INT16_MAX));
for(int i=0;i<=n;i++){
dp[i][0]=0;
}
cout<<"now the dp is :"<<endl;
for(int xx=0;xx<dp.size();xx++){
for(int yy=0;yy<dp[0].size();yy++){
cout<<yy<<"-"<<dp[xx][yy]<<" ";
}
cout<<endl;
}
cout<<"now record is: "<<endl;
for(int xx=0;xx<record.size();xx++){
cout<<"volume-"<<xx<<"-";
for(int yy=0;yy<record[xx].size();yy++){
cout<<record[xx][yy]<<" ";
}
cout<<endl;
}
for(int i=1;i<=n;i++){
for(int j=v[i-1];j<=m;j++){
//如果上一个物品这个容量还不能恰好放入，或者这个物体新放入还不能恰好放入
//那么优先记录能成功恰好放入的情况
//而不去做题目需要的“最小”判断，记录恰好放入和记录最小是冲突的
//简洁写法，利用负值特性
/**
if(dp[i-1][j]<0 || dp[i][j-v[i-1]]<0){
dp[i][j]=max(dp[i-1][j],dp[i][j-v[i-1]]+1); //这一句的作用并非不更新，而是更新之后如果不成功应该还为负值（因为初始化了-INT_MAX）
cout<<j<<'-'<<dp[i][j]<<' ';
continue;
}
*/
//完全背包的遍历，从自己物体这一轮次取值
//完整情况判断，注意要可以取0值
if(dp[i-1][j]<0 && dp[i][j-v[i-1]]<0) {
continue;
}
if(dp[i-1][j]>=0 && dp[i][j-v[i-1]]<0) {
dp[i][j]=dp[i-1][j];
continue;
}
if(dp[i-1][j]<0 && dp[i][j-v[i-1]]>=0) {
dp[i][j]=dp[i][j-v[i-1]]+1;
record[j]=record[j-v[i-1]];
record[j].push_back(i);
continue;
}
if(dp[i-1][j]>=0 && dp[i][j-v[i-1]]>=0){
//当上一个物品这个容量dp[i-1][j]恰好装入且和放入这个物体之前dp[i][j-v[i-1]]恰好装入的情况下，
//那从dp[i][j-v[i-1]]再放入这个物体也是恰好装入的，可以比较题意要求的较小值
//简洁写法，只需要记录数量的话
//dp[i][j]=min(dp[i-1][j],dp[i][j-v[i-1]]+1);
if(dp[i-1][j]>dp[i][j-v[i-1]]+1){
dp[i][j]=dp[i][j-v[i-1]]+1;
record[j]=record[j-v[i-1]];
record[j].push_back(i);
}else{
dp[i][j]=dp[i-1][j];
}
}
}
cout<<"now the dp is :"<<endl;
for(int xx=0;xx<dp.size();xx++){
for(int yy=0;yy<dp[0].size();yy++){
cout<<yy<<"-"<<dp[xx][yy]<<" ";
}
cout<<endl;
}
cout<<"now record is: "<<endl;
for(int xx=0;xx<record.size();xx++){
cout<<"volume-"<<xx<<"-";
for(int yy=0;yy<record[xx].size();yy++){
cout<<record[xx][yy]<<" ";
}
cout<<endl;
}
}
}
多维背包
增加限制条件只需要进一步嵌套。
//01背包，三个限制
void dim3Bag(vector<int> v,vector<int> w1,vector<int> w2,vector<int> w3,int w1_volume,int w2_volume,int w3_volume){
// 定义一个x*y*z的三维vector
int x = w3_volume+1, y = w2_volume+1, z = w1_volume+1;
vector<vector<vector<int>>> dp(x, vector<vector<int>>(y, vector<int>(z)));
// 用嵌套循环初始化vector
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
for (int k = 0; k < z; k++) {
dp[i][j][k] = 0;
}
}
}
for(int item=0;item<w1.size();i++){
for(int w1_j=w1_volume;w1_j>item;w1_j--){
for(int w2_j=w2_volume;w2_j>item;w2_j--){
for(int w3_j=w3_volume;w3_j>item;w3_j--){
dp[w1_j][w2_j][w3_j]=max(dp[w1_j-1][w2_j][w3_j],dp[w1_j-w1[item]][w2_j-w2[item]][w3_j-w3[item]]+v[item])
}
}
}
}
cout << dp[w1_volume][w2_volume][w3_volume] << endl;
}