01背包问题
f[i][j] i代表前i件物品，j代表体积。
属性 ：max;
f[i][j]=f[i-1][j] w[i]<j
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
朴素算法

#include<iostream>
using namespace std;

int n,m;//数量 容量
int v[1010],w[1010];//体积 价值
int f[1010][1010];//最大价值
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=f[i-1][j];
 if(j>=v[i])
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]); 
}
}
cout<<f[n][m];
 return 0;
}

空间优化一维数组

#include<iostream>
using namespace std;
int n,m;//数量 容量
int v[1010],w[1010];//体积 价值
int f[1010];//最大价值
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
 for(int i=1;i<=n;i++){
 for(int j=m;j>=v[i];j--){
 f[j]=max(f[j],f[j-v[i]]+w[i]);}
}
cout<<f[m];
return 0;
}

完全背包问题
f[i][j] i代表前i件物品 j代表容量
属性 max
f[i][j]=f[i-1][j] w[i]<j;

f[i][j]=max(f[i-1][j],f[i-1][j - k * w[i] ]+k * w[i])
k * w[i]>=j;

f[i][j]=max(f[i-1][j],f[i][j-w[i]]) w[i]>=j;
朴素算法1

#include<iostream>
using namespace std;
int n,m;//数量 容量
int v[1010],w[1010];//体积 价值
int f[1010][1010];//最大价值
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
 for(int j=1;j<=m;j++){
 f[i][j]=f[i-1][j];
 if(j>=v[i])
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
}
cout<<f[n][m];
 return 0;
}

空间优化算法

#include<iostream>
using namespace std;
int n,m;//数量 容量
int v[1010],w[1010];//体积 价值
int f[1010];//最大价值
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
 for(int i=1;i<=n;i++){
for(int j=v[i];j<=m;j++){
 f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m];
return 0;
}

多重背包问题
f[i][j] i代表前i件物品，j代表体积
f[i][j]=f[i-1][j] 不选i;
f[i][j]=f[i-1][j-kw[i]]+kv[i] k*w[i]<=j;
朴素算法

#include<iostream>
using namespace std;
const int N = 1101;
int f[N];
int w[N],v[N],c[N];
int main( )
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i]>>c[i];
        for(int j=m;j>=v[i];j--)
        for(int k=0;k<=c[i]&&k*v[i]<=j;k++)
        {
            f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
        }

    }
    cout<<f[m];


    return 0;
    } 

二进制优化算法

#include<iostream>
using namespace std;
const int X=2001;
int n,m;//物品种数,背包容量
int v,w,s;
int vv[X*12],ww[X*12];//2的12次方大于2000，也就是说一个数最多可以拆成12个，故数组容量乘12
int f[X];//最优解
int main()
{
int i,j;
cin >>n >>m;
int num=1; //拆分计数
for(i=1;i<=n;i++){
//v,w,s;体积,价值,数量
cin >>v >>w >>s;
//二进制拆分
 for(j=1;j<=s;j<<=1){
 vv[num]=j*v; //存体积
 ww[num++]=j*w;//存价值
 s-=j;
 }
if(s){ //剩余
 vv[num]=s*v;
 ww[num++]=s*w;
 }
}
//01背包
for(i=1;i<num;i++)
for(j=m;j>=vv[i];j--)
f[j]=max(f[j],f[j-vv[i]]+ww[i]);
cout<<f[m];
return 0;
}

混合背包
由01背包 多重背包 完全背包组成
第一种做法

#include <iostream>
using namespace std;
const int N=1010,M=10000;
int f[N];
int a[M],b[M],c[M];
int n, m;
int main()
{
 cin >> n >> m;
 int v, w, s;
 int num = 1;
 for(int i=1; i<=n; i++){
 scanf("%d%d%d",&v,&w,&s);
 if(s==0){ //完全背包
 a[num] = v;
 b[num] = w;
 c[num++]=0;//背包类型
 }
 else{
 if(s==-1)
s=1; //01背包转多重背包
 int k = 1;
 while(s>=k){//二进制拆分
 a[num] = k*v;
 b[num] = k*w;
 c[num++] = 1;//背包类型
 s -= k;
 k <<= 1;
 }
 if(s){
 a[num] = s*v;
 b[num] = s*w;
 c[num++] = 1;
 }
 }
 }
 //做一遍两类背包
 for (int i=1; i<num; i++){
 if(c[i]==1) //01背包
 for(int j=m; j>=a[i]; j--)
 f[j]=max(f[j],f[j-a[i]]+b[i]);
 else //完全背包
 for(int j=a[i]; j<=m; j++)
 f[j]=max(f[j],f[j-a[i]]+b[i]);
 }
 cout<<f[m]<<endl;
 return 0;
}