01背包问题(01knapsack)

最基本的背包问题就是 01 背包问题:背包承重为 Capacity, 现在有n个物品,物品重量 w[n], 物品价值 v[n]。如何选择物品价值最⼤?

方法一、每个物品都有两种可能性,装到背包里或不装到背包里!n个物品总共有2n次可能性。遍历所有的可能性,找到可装最大价值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**************************************************************** 
 * Description: C++ implementation of Knapsack Brute force
 * Author: Alex Li
 * Date: 2023-06-20 06:27:38
 * LastEditTime: 2023-06-20 06:33:55
****************************************************************/
#include<iostream>
using namespace std;
const int N = 100;
int n, w;
int W[N], V[N];

//从第i个物品开始挑选总重小于j的部分
int solve(int i, int j){
	int result;
	if (i == n)//已经没有剩余的物品了
	    result= 0;
	else if (j < W[i]) 
		result = solve(i + 1, j);//如果i物品的重量大于背包剩余重量,就选下一个物品试试
	else	{
        //一个物品选还是不选都试一下,选最大的返回。
		result = max(solve(i + 1, j), solve(i + 1, j - W[i]) + V[i]);
	}
	return result;
}
int main()
{
	cin >> n >> w;
	for (int i = 0; i < n; i++)
		cin >> W[i]>>V[i];
		cout << solve(0, w) << endl;
	return 0;
}


方法二:动态规划
时间复杂度O(nw)

对于第i物品,只有两种可能,一是选择该物品,二是不选择该物品。
如果选择该物品,则需要在前i-1个物品中选择若干个使得体积和不超过V-vi的物品。
如果不选择该物品,则需要在前i-1个物品中选择若干个使得体积和不超过V的物品
注:V是背包的容量,vi是i物品的体积。

商品
种类


背包承重
1 2 3 4 5 6 7 8 9 10 11 12
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 6 1 6 7 7 7 7 7 7 7 7 7 7
3 5 18 1 6 7 7 18 19 24 25 25 25 25 25
4 6 22 1 6 7 7 18 22 24 28 29 29 40 41
5 7 28 1 6 7 7 18 22 28 29 34 35 40 46
6 10 41 1 6 7 7 18 22 28 29 34 41 42 47


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**************************************************************** 
 * Description: C++ implementation of 0-1 KnapSack
 * Author: Alex Li
 * Date: 2022-04-23 15:40:21
 * LastEditTime: 2023-06-20 10:43:48
****************************************************************/
#include <iostream>
using namespace std;

int dp[35][205];  ////记录统计数据
int weight[35];  //存储各商品的重量
int value[35];  //存储各商品的价值
int choose[35];

//回溯一下,看看哪些商品被用到了。
void flashBack(int m,int n){
    int i=n,j=m;
    int k=0;
    while (i!=0){
        if(dp[i][j]==dp[i-1][j])
        i--;
        else{
           choose[k]=i;
           j=j-weight[i];
           k++;
           i--;
        }
    }
}
int main(){
    int m,n;  //n为商品个数,m为背包容量(重量)
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>weight[i]>>value[i];   //l输入每个商品的 重量和价值 
    }
    for (int i = 1; i <=n; i++){    //逐个遍历每个商品
        for (int j = 1; j <=m; j++){  //求出从 1 到 m 各个载重对应的最大收益
            if(j<weight[i])        //如果i商品的重量大于背包的容量,哪就不装该商品
                dp[i][j]=dp[i-1][j]; //当i等于0时,dp[0][i]都在数组创建时,赋值为零。 
            else   //比较不装入该商品和装入该商品,哪种情况获得的收益更大,记录最大收益值
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]); 
                //dp[i-1][j]是不装入i商品的价值
                //d[i-1][j-weight[i]]是指减掉i商品的重量后,剩余的背包容量能装商品的价值
                //d[i-1][j-weight[i]]+value[i]加上i商品后的背包价值
        }
    }
    cout<<"max value in knapsack is: "<<dp[n][m]<<endl;  //输出结果
    //回溯被商品
    flashBack(m,n);
    //输出被选择的商品
    cout<<"which article is choosed: ";
    for (int i = 0; i <n; i++){
        if(choose[i]==0)break;
        else cout<<choose[i]<<' ';
    }
    
    cout<<endl;
    //输出dp表看变化
    cout<<"print dp array: "<<endl;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j<=m ; j++){
            if(dp[i][j]/10==0)cout<<' ';
            cout<<dp[i][j]<<"  ";
        }
        cout<<endl;
    }
    
}


方法三:利用滚动数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**************************************************************** 
 * Description: C++ implementation of 0-1 KnapSack pro 
 * Author: Alex Li
 * Date: 2022-04-23 15:40:21
 * LastEditTime: 2023-06-19 21:51:19
****************************************************************/
#include <iostream>
using namespace std;

const int MAXN=10000;  //物品最大数量
const int MAXV=10000;  //背包最大容量
int N;  //储存物品的实际个数
int V;  //背包实际的容量
int dp[MAXN];  ////滚动数组记录统计数据
int weight[MAXN];  //存储各商品的重量
int value[MAXN];  //存储各商品的价值
int main(){
    cin>>N>>V; //输入物品个数和背包容量 
    //l输入每个商品的 重量和价值 
    for(int i=1;i<=N;i++)cin>>weight[i]>>value[i];  
       
    //边界初始化,全局数组默认值也是0,所以为段代码不写也不影响结果。
    for (int i = 0; i <=V; i++)dp[i]=0;    
    
    for (int i = 1; i <=N; i++){    //逐个遍历每个商品
        for (int j = V; j >=weight[i]; j--){//如果i物品容量大于背包容量,for循环就停止,该物品装不进行。
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]); 
            //从背包大数值开始,反向生成动态数组
         }
    }
    cout<<dp[V]<<endl;  //输出结果
    
}

洛谷:AT_dp_d

Scroll to Top