跳转至

0-1背包问题

 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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//动态规划法求解0-1背包问题 
#include <iostream>

using namespace std;

int max(int a, int b) {  //求a，b元素中的最大值 
    return (a > b) ? a : b;
}

int min(int a, int b) {  //求a，b元素中的最小值 
    return (a < b) ? a : b;
}

//求背包中物体总价值的最大值 
void knapsack(int itemSize[], int itemValue[], int capacity, int itemNumber, int **m) {
    //物体数量为itemNumber，物体i的体积为itemsize[i]，价值为itemValue[i]，背包容量为capacity
    //m[itemNumber+1][capacity+1]存储动态规划表
    //m[i][j]表示第i..itemNumber个物体在背包容量为j时背包所能装入的最大价值 
    int jMax = min(itemSize[itemNumber] - 1, capacity); 
    int j;
    for (j = 0; j <= jMax; j++) {
        m[itemNumber][j] = 0;
    }
    for (j = itemSize[itemNumber]; j <= capacity; j++) {
        m[itemNumber][j] = itemValue[itemNumber];
    }
    int i;
    for (i = itemNumber - 1; i >= 2; i--) { //i>1，表示对i=1暂时不处理，i=1时只需求m[1][capacity] 
        jMax = min(itemSize[i] - 1, capacity);
        for (j = 0; j <= jMax; j++) {
            m[i][j] = m[i + 1][j];
        }
        for (j = itemSize[i]; j <= capacity; j++) {
            m[i][j] = max(m[i + 1][j], m[i + 1][j - itemSize[i]] + itemValue[i]);
        }
    }
    if (capacity >= itemSize[1]) {
        m[1][capacity] = max(m[2][capacity], m[2][capacity - itemSize[1]] + itemValue[1]);
    }
    else {
        m[1][capacity] = m[2][capacity];
    }
}

//回溯输出解x[1..itemNumber] 
void traceback(int itemSize[], int capacity, int itemNumber, int **m, int *x) {
    int i;
    for (i = 0; i < itemNumber; i++) {
        //在背包容量为capacity时，考虑有第i..itemNumber个物体和有第i+1..itemNumber个物体
        //如果二者的最大价值相同，则说明第i个物体未放入背包。 
        if (m[i][capacity] == m[i+1][capacity]) {  
            x[i] = 0;
        }
        else {  //否则说明第i个物体放入背包 
            x[i] = 1;  
            capacity -= itemSize[i]; //背包容量减去第i个物体的体积 
        }
    }
    x[itemNumber] = (m[itemNumber][capacity]) ? 1 : 0;
}

int main() {
    int capacity = 55;
    int itemNumber = 14;
    int itemSize[] = {0, 3, 5, 11, 7, 9, 2, 13, 17, 26, 24, 19, 14, 12, 6};
    int itemValue[] = {0, 5, 7, 15, 8, 9, 1, 10, 17, 30, 26, 20, 17, 9, 6};
    //为动态规划表m，解向量x开空间 
    int **m = new int*[itemNumber + 1];
    int i;
    for (i = 0; i < itemNumber + 1; i++) {
        m[i] = new int[capacity + 1];
    } 
    int *x = new int[itemNumber + 1];

    knapsack(itemSize, itemValue, capacity, itemNumber, m);
    traceback(itemSize, capacity, itemNumber, m, x);
    for (i = 1; i <= itemNumber; i++) { //输出解x[1..itemNumber]，一个01序列，0代表没选，1代表选中 
        cout << x[i] << " ";
        if (i == itemNumber) {
            cout << endl;
        }
    }
    for (i = 1; i <= itemNumber; i++) { //输出装入背包的物体编号 
        if (x[i] == 1) {
            cout << "Item " << i << " is chosen, ";
            cout << "its value is " << itemValue[i] << ", its size is " << itemSize[i] << endl; 
        }
    }  
    cout << "The optimal solution (the largest value of the knapsack) is ";
    cout << m[1][capacity] << endl; //输出最优解，即背包中物体总价值的最大值 
    //释放动态规划表m，解向量x占据的空间 
    for (i = 0; i < itemNumber + 1; i++) {
        delete[]m[i]; 
    } 
    delete[]m;
    delete[]x;
    return 0;
}