首页 > 代码库 > 动态规划——0-1背包问题

动态规划——0-1背包问题

2024-07-02 10:03:10   231人阅读

 0-1背包问题：

　　描述：给定n中物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c，问应如何选择装入背包中的物品，使得装入背包中的物品总价值最大？

　　0-1背包问题是一个特殊的整数规划问题。

　　　　　　

　　设所给0-1背包问题的子问题;

　　　　　　　　

　　其最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下:

　　　　　　

NO1：递归实现

 1 /*
 2 *Description 递归实现
 3 *设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。 
 4 *问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。 
 5 *如果有满足条件的选择，则此背包有解，否则此背包问题无解。
 6 */
 7 # include<stdio.h>
 8 # include<string.h>
 9 
10 int date[1005];
11 
12 int f(int w,int s)
13 {
14     if(w==0) return 1;//正好
15     if(w<0||w>0 &&s==0) return 0;
16     if(f(w-date[s],s-1)) return 1;//退出来再选下一个 
17     return f(w,s-1);//选择下一个
18 }
19 
20 int main()
21 {
22     int i,Weight,n;
23     while(scanf("%d %d",&Weight,&n)!=EOF)
24     {
25         memset(date,0,sizeof(date));
26         for(i=1;i<=n;i++)
27             scanf("%d",&date[i]);
28         if(f(Weight,n))
29             printf("YES\n");
30         else 
31             printf("NO\n");
32     }
33     return 0;
34 }
递归实现代码

 

NO2：动态规划——从后往前实现

 1 /*
 2 *从后往前得到最终结果
 3 *二维数组m[][]来存储m(i,j)的相应值
 4 *i：物品的取值范围(i,n)
 5 *j：当前背包的最大容量值
 6 */
 7 
 8 #include <stdio.h>
 9 #include <stdlib.h>
10 #include <math.h>
11 #include <windows.h>
12 
13 # define max(a,b) a>b?a:b
14 # define min(a,b) a<b?a:b
15 
16 void Knapsack(int *v, int *w,int c, int n, int m[][100])
17 {
18     int i,j,jmax;
19     jmax=min(w[n]-1, c);         //装不下n号物品的最大重量
20     for(j = 0; j <= jmax; j++)
21         m[n][j] = 0;
22     for(j = w[n]; j <= c; j++)
23         m[n][j] = v[n];
24     for(i = n-1; i > 1; i--)
25     {
26         jmax = min(w[i]-1, c);
27         for(j = 0; j <= jmax; j++)
28             m[i][j] = m[i+1][j];
29         for(j = w[i]; j <= c; j++)
30             m[i][j] = max(m[i+1][j],m[i+1][j - w[i]] + v[i]);
31     }
32     m[1][c] = m[2][c];
33     if(c >= w[1])
34         m[1][c] = max(m[2][c],m[2][c - w[1]] + v[1]);
35 }
36 
37 void Traceback(int m[][100], int *w, int c, int n, int *x)
38 {
39     int i;
40     for(i = 1; i < n; i++)
41         if(m[i][c] == m[i + 1][c])
42             x[i] = 0;
43         else
44         {
45             x[i] = 1;
46             c -= w[i];            //背包容量的变化，逐渐减少
47         }
48         x[n] = (m[n][c]) ? 1 : 0;
49 }
50 
51 void main()
52 {
53     int j;
54     int i,n,c;
55     int v[100]={0},w[100]={0};
56     int m[100][100] = {0};
57     int x[100]={0};
58 
59     printf("please input the num : n = ");
60     scanf("%d",&n);
61     printf("\nplease input the capacitance : c = ");
62     scanf("%d",&c);
63     printf("\nplease input the value :\n");
64     for(i = 1; i <= n; i++)
65         scanf("%d",&v[i]);
66     printf("\nplease input the weight :\n");
67     for(i = 1; i <= n; i++)
68         scanf("%d",&w[i]);
69 
70     Knapsack(v,w,c,n,m);
71 
72     Traceback(m,w,c,n,x);
73 
74     printf("\nthe result is :");
75     for(i = 1; i <= n; i++)
76         if(x[i]==1)
77             printf("%d  ",i);
78     Sleep(10000000);
79 
80 }
动态规划代码——从后往前

 

NO3：动态规划——从前往后实现

  1 /*
  2 *从前往后得到最终结果
  3 *二维数组m[][]来存储m(i,j)的相应值
  4 *i：物品的取值范围(1，i)
  5 *j：当前背包的最大容量值
  6 */
  7 
  8 #include <stdio.h>
  9 #include <stdlib.h>
 10 #include <math.h>
 11 #include <windows.h>
 12 
 13 # define max(a,b) a>b?a:b
 14 # define min(a,b) a<b?a:b
 15 
 16 void Knapsack(int *v, int *w,int c, int n, int m[][100])
 17 {
 18     int i,j,jmax;
 19     jmax=min(w[n]-1, c);
 20     for(j = 0; j <= jmax; j++)
 21         m[n][j] = 0;
 22     for(j = w[n]; j <= c; j++)
 23         m[n][j] = v[n];
 24     for(i = n-1; i > 1; i--)
 25     {
 26         jmax = min(w[i]-1, c);
 27         for(j = 0; j <= jmax; j++)
 28             m[i][j] = m[i+1][j];
 29         for(j = w[i]; j <= c; j++)
 30             m[i][j] = max(m[i+1][j],m[i+1][j - w[i]] + v[i]);
 31     }
 32     m[1][c] = m[2][c];
 33     if(c >= w[1])
 34         m[1][c] = max(m[2][c],m[2][c - w[1]] + v[1]);
 35 }
 36 
 37 void Traceback(int m[][100], int *w, int c, int n, int *x)
 38 {
 39     int i;
 40     for(i = 1; i < n; i++)
 41         if(m[i][c] == m[i + 1][c])
 42             x[i] = 0;
 43         else
 44         {
 45             x[i] = 1;
 46             c -= w[i];
 47         }
 48         x[n] = (m[n][c]) ? 1 : 0;
 49 }
 50 
 51 void Knapsack_pre(int *v, int *w,int c, int n, int m[][100])
 52 {
 53     int i,j,jmax;
 54     jmax=min(w[1]-1, c);
 55     for(j = 0; j <= jmax; j++)
 56         m[1][j] = 0;
 57     for(j = w[1]; j <= c; j++)
 58         m[1][j] = v[1];
 59     for(i = 2; i <= n; i++)
 60     {
 61         jmax = min(w[i]-1, c);
 62         for(j = 0; j <= jmax; j++)
 63             m[i][j] = m[i-1][j];
 64         for(j = w[i]; j <= c; j++)
 65             m[i][j] = max(m[i-1][j],m[i-1][j - w[i]] + v[i]);
 66     }
 67 }
 68 
 69 void Traceback_pre(int m[][100], int *w, int c, int n, int *x)
 70 {
 71     int i;
 72     for(i = n; i > 0; i--)
 73         if(m[i][c] == m[i - 1][c])
 74             x[i] = 0;
 75         else
 76         {
 77             x[i] = 1;
 78             c -= w[i];
 79         }
 80         x[1] = (m[1][c]) ? 1 : 0;
 81 }
 82 
 83 void main()
 84 {
 85     int j;
 86     int i,n,c;
 87     int v[100]={0},w[100]={0};
 88     int m[100][100] = {0};
 89     int x[100]={0};
 90 
 91     printf("please input the num : n = ");
 92     scanf("%d",&n);
 93     printf("\nplease input the capacitance : c = ");
 94     scanf("%d",&c);
 95     printf("\nplease input the value :\n");
 96     for(i = 1; i <= n; i++)
 97         scanf("%d",&v[i]);
 98     printf("\nplease input the weight :\n");
 99     for(i = 1; i <= n; i++)
100         scanf("%d",&w[i]);
101 
102     Knapsack_pre(v,w,c,n,m);
103 
104     Traceback_pre(m,w,c,n,x);
105 
106     printf("\n\n");
107     printf("m :\n");
108     for(i = 1; i <= n; i++)
109     {
110         for(j = 0; j <= c; j++)
111             printf("%d   ",m[i][j]);
112         printf("\n");
113     }
114 
115     printf("\n\n");
116     printf("x : \n");
117     for(i = 1; i <= n; i++)
118         printf("%d   ",x[i]);
119 
120     printf("\nthe result is :");
121     for(i = 1; i <= n; i++)
122         if(x[i]==1)
123             printf("%d  ",i);
124     Sleep(10000000);
125 
126 }
动态规划代码——从前往后

 

NO4：自顶向下的递归实现 + 自底向上实现 + 基于备忘录的自顶向下实现

  1 #include <stdio.h>
  2 
  3 #define N    4
  4 #define W    5
  5 
  6 //物品的重量
  7 int w[] = {-1, 2, 1, 3, 2};
  8 
  9 //价值数组
 10 int vi[] = {-1, 12, 10, 20, 15};
 11 
 12 int v[N+1][W+1]; //v[i][j]表示从前i个物品选能够放进承重量为j的背包的子集的最大总价值
 13 
 14 void init()
 15 {
 16     int  i, j;
 17     for (i = 0; i <= N; i++)
 18         for (j = 0; j <= W; j++)
 19             v[i][j] = -1;
 20 
 21     for (i = 0; i <= N; i++)
 22         v[i][0] = 0;
 23 
 24     for (i=0; i <= W; i++)
 25         v[0][i] = 0;
 26 }
 27 
 28 
 29 //基于备忘录的动态规划算法
 30 int MKFnapsack_MEMOIZE(int i, int j)
 31 {
 32     int value;
 33     if (v[i][j] < 0)  //如果v[i][j]还没有计算,则进行计算
 34     {
 35         if (j < w[i])
 36             value = http://www.mamicode.com/MKFnapsack_MEMOIZE(i-1,j);
 37         else
 38         {
 39             int v1 = MKFnapsack_MEMOIZE(i-1, j);
 40             int v2 = MKFnapsack_MEMOIZE(i-1, j-w[i]) + vi[i];
 41             value = http://www.mamicode.com/v1 >=v2 ? v1:v2;
 42         }
 43         v[i][j] = value;
 44     }
 45     return v[i][j]; //如果v[i][j]已经进行计算,则不进行计算,直接返回即可
 46 }
 47 
 48 //自顶向下的动态规划算法
 49 int MKFnapsack_TOP_TO_BOTTOM(int i, int j)
 50 {
 51     int value;
 52     
 53     if(i <= 0 || j <= 0)
 54         return 0;
 55 
 56     //不管v[i][j]是否计算过,都进行计算
 57     if (j < w[i])
 58         value = http://www.mamicode.com/MKFnapsack_TOP_TO_BOTTOM(i-1, j);
 59     else
 60     {
 61         int v1 = MKFnapsack_TOP_TO_BOTTOM(i-1, j);
 62         int v2 = MKFnapsack_TOP_TO_BOTTOM(i-1, j-w[i]) + vi[i];
 63         value = http://www.mamicode.com/v1 >= v2 ? v1:v2;
 64     }
 65 
 66     return value;
 67 }
 68 
 69 //自底向上的算法
 70 int MKFnapsack_BOTTOM_TO_TOP(int Ni, int Wi)
 71 {
 72     int i, j;
 73     for (i = 1; i <= Ni; i++)
 74     {
 75         for(j = 1; j <= Wi; j++)
 76         {
 77             if(j < w[i])
 78                 v[i][j] = v[i-1][j];
 79             else //j >=w[i]
 80             {
 81                 int v1= v[i-1][j];
 82                 int v2 = v[i-1][j-w[i]] + vi[i];
 83                 v[i][j] = v1 >= v2 ? v1:v2;
 84             }
 85         }
 86     }
 87     return v[N][W];
 88 }
 89 
 90 void print_v(int Ni, int Wi)
 91 {
 92     int i, j;
 93     for(i = 0; i <= Ni; i++)
 94     {
 95         for(j = 0; j <= Wi; j++)
 96             printf("%d ", v[i][j]);
 97         printf("\n");
 98     }
 99 }
100 
101 int main()
102 {
103     printf("top to bottom most value is:%d\n", MKFnapsack_TOP_TO_BOTTOM(N, W));
104 
105     init();//数组初始化
106     printf("memoize most value is:%d\n", MKFnapsack_MEMOIZE(N, W));
107     print_v(N, W);
108 
109     init();
110     printf("bottom to top most value is:%d\n", MKFnapsack_BOTTOM_TO_TOP(N, W));
111     print_v(N, W);
112 
113     return 0;
114 }

 分析：

　　自顶向下的递归算法，写法最简单，但效率是最低的，它往往把问题搞成指数级。而自底向上的算法是DP的经典策略，它比自顶向下的效率高，但是，它往往也计算了没有必要计算的子问题(见上图)。而基于备忘录的自顶向下的算法是前两者的集大成者，效率最优。

 


联系
我们