背景

给定一个容量为t的背包和n个价值v[i]和体积为w[i]的物体，问怎么选取这些物体，且不超过背包的称重，让所取的子集达到最大价值。

背包问题

  1. 0/1背包
  2. 完全背包
  3. 多重背包

0/1背包

背景

给定一个容量为t的背包和n种价值v[i]和体积为w[i]的物体（每个物体只能选择一次）

难点

由于背包问题中n个物体一共有2^n个子集，穷举法的时间复杂度为O(2^n),除非n很小，否则会出超时错误。

思路

假设物体有n-1个，且在背包容量为0，1，2，3，……，t的各个情况下所能得到最大价值已经知道，那么当我们多考虑一个物体，即物体有n个时，就可以分为两种情况进行考虑

  1. 第n个物体不放进背包，最大价值同n-1个物体的最大价值
  2. 第n个物体放进背包，最大价值为（本物体的价值）+（空间为t-w[n]时只考虑n-1的所能达到的最大价值）

二维数组

#include<iostream>
#include<cmath>

using namespace std;

int main(){
    int t=0,n=0;
    int f[101][1001]={},w[101]={},v[101]={};    
    cin>>t>>n;    
    for(int i=1;i<=n;i++){
            cin>>w[i]>>v[i];
            }   
    for(int i=1;i<=n;i++){
            for(int j=1;j<=t;j++){
                    if(j<w[i]){
                               f[i][j]=f[i-1][j];
                               }
                    else{
                         f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
                         }                    
                    }
            }
    cout<<f[n][t];    
    return 0;
    }

一维数组

#include<iostream>
#include<cmath>

using namespace std;

int main(){
	int t=0,m=0;
	int f[1001]={},v[101]={},w[101]={};
	cin>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=m;i++){
		//需要注意这里是逆向循环，因为只有一个i，需要知道选择i之前的总价值
		for(int j=t;j>=w[i];j--){
			f[j]=max(f[j-w[i]]+v[i],f[j]);
		}
	}
	cout<<f[t];
	return 0;
}

完全背包

背景

给定一个容量为t的背包和n种价值v[i]和体积为w[i]的物体（每个物体可以无限次选取）

难点

每种有无数件，所以比0/1背包情况更多，更不可能用枚举的方法。

思路

虽然每种有无数件，但是背包容量是固定的导致每种最多只能取某个值，再多就放不下了，这个值就是t/w[i]。即对第i种物品，可以取0，1，2……t/w[i]件。

F（i，j）= max{ F(i-1,j-kw[i])+kv[i] } ，0≤k*w[i]≤t，i=0,1……,n，j=0,1……t

二维数组

#include<iostream>
#include<cmath>

using namespace std;

int main(){
    int t=0,n=0;
    int  f[101][1001]={},w[101]={},v[101]={}; 
    cin>>t>>n;
    for(int i=1;i<=n;i++){
            cin>>w[i]>>v[i];
            }
    for(int i=1;i<=n;i++){
            for(int j=1;j<=t;j++){
                    f[i][j]=f[i-1][j];
                    if(j<w[i])
                          continue;
                    else {
                         int tempMax=f[i][j];
                         for(int k=1;k<=j/w[i];k++){
                                 tempMax=max(tempMax,f[i-1][j-k*w[i]]+k*v[i]);
                                 }
                         f[i][j]=tempMax;
                         }
                    }
            }
    cout<<f[n][t];
    return 0;
    }

一维数组

#include<iostream>
#include<cmath>

using namespace std;

int main(){
    int t=0,n=0;
    int f[100001]={},w[10001]={},v[10001]={};
    cin>>t>>n;
    for(int i=1;i<=n;i++){
            cin>>w[i]>>v[i];
            }
    for(int i=1;i<=n;i++){
            //这里正序循环，是因为不再限制物品的个数，同时省了一层循环
            for(int j=w[i];j<=t;j++){
                    f[j]=max(f[j],f[j-w[i]]+v[i]);
                    }
            }
    cout<<f[t];
    return 0;
    }

多重背包

背景

给定一个容量为t的背包和N个价值v[i]和体积为w[i]的物体（每个物体最多有n[i]个）

解法

思路

类似于完全背包，只不过每个物品选取的上限要同时受背包容量和物体最大个数影响

二维数组

#include<iostream>
#include<cmath>

using namespace std;

int main(){
    int t=0,N=0;
    int f[101][1001]={},w[101]={},v[101]={},n[101]={};
    
    cin>>t>>N;
    for(int i=1;i<=N;i++){
            cin>>w[i]>>v[i]>>n[i];
            }
    for(int i=1;i<=N;i++){
            for(int j=1;j<=t;j++){
                    if(n[i]==0||j<w[i]){
                                        f[i][j]=f[i-1][j];
                                        continue; 
                                        }
                    for(int k=1;k<=n[i]&&k<=j/w[i];k++){
                            f[i][j]=max(f[i-1][j],f[i-1][j-k*w[i]]+k*v[i]);
                            }
                    }
            }
            
    cout<<f[N][t];
    return 0;
    }

一维数组实现

//多重背包的一维数组实现实际上是多了一步处理：
//将第i种的n[i]个同种物品看作n[i]个不同种物品，只不过恰好价值和体积相同
//然后每个物品只能拿一次
//即转化为了0/1背包问题