0%

背包问题

发表于 更新于 分类于 ，

前言

0/1背包问题

  • 给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，对每种物品i只有两种选择：装入背包或不装入背包，如何选择装入背包的物品，使得装入背包的物品的总价值最大？

算法思路

例如，对于n=3的0/1背包问题，其空间树如图，树种第i层与第i+1层结点之间的边上给出了对物品i的选择结果，左子树表示该物品被装入了背包，右子树表示该物品没有被装入背包。树种的8哥叶子结点分别代表该问题的8个可能解，例如结点8代表一个可能解（1，0，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
#include <iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>

using namespace std;

#define N 100

struct goods{
    int wight;//物品重量
    int value;//物品价值
};

int n,bestValue,cv,cw,C;//物品数量，价值最大，当前价值，当前重量，背包容量
int X[N],cx[N];//最终存储状态，当前存储状态
struct goods goods[N];

int BackTrack(int i){
    if(i > n-1){
        if(bestValue < cv){
            for(int k = 0; k < n; k++)
                X[k] = cx[k];//存储最优路径
            bestValue = cv;
        }
        return bestValue;
    }
    if(cw + goods[i].wight <= C){//进入左子树
        cw += goods[i].wight;
        cv += goods[i].value;
        cx[i] = 1;//装入背包
        BackTrack(i+1);
        cw -= goods[i].wight;
        cv -= goods[i].value;//回溯，进入右子树
    }
    cx[i] = 0;//不装入背包
    BackTrack(i+1);
    return bestValue;
}

bool m(struct goods a, struct goods b){
    return (a.value/a.wight) > (b.value/b.wight);
}

int KnapSack3(int n, struct goods a[], int C,int x[N]){
    memset(x,0,sizeof(x));
    sort(a,a+n,m);//将各物品按单位重量价值降序排列
    BackTrack(0);
    return bestValue;
}
int main()
{
    printf("n:");
    scanf("%d",&n);
    printf("C:");
    scanf("%d",&C);
    for(int i = 0; i < n; i++){
        printf("weight and value:",i+1,i+1,i+1);
        scanf("%d%d",&goods[i].wight,&goods[i].value);
    }
    int sum3 = KnapSack3(n,goods,C,X);
    printf("The answer\nX=[");
    for(int i = 0; i < n; i++)
        cout << X[i] <<" ";//输出所求X[n]矩阵
    printf("]   The value%d\n",sum3);
    return 0;
}

运行结果

2