背包动态规划-01背包(01knapsack)

 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;
}

 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;  //输出结果
    
}