0-1背包_回溯法

 1 procedure work(k,wei:integer);
 2     var i,j:integer;
 3     for i:=1 downto 0 do
 4         if  (wei-w[k]*i>=0) 
 5           {
 6            bag[k]:=i;
 7            count:=count+v[k]*i;
 8            if (k=n) and (count>best)
 9              {best:=count;
10               for j:=1 to n do y[j]:=bag[j];
11              }
12            if k<n then work(k+1,wei-w[k]*i);
13            count:=count-c[k]*i;    {状态恢复}
14            }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int v[10];//物品的价值
 4 int bag[10];//记录解空间物品的状态1为装入0为没有装入
 5 int w[10];//每个物品的重量
 6 int y[10];//记录最佳装载的方案
 7 int count1=0;//记录该装载方案的总价值
 8 int best=0;//记录最佳装载方案的总价值
 9 void procedure(int k,int wei,int N)
10 {
11 
12     for(int i=0;i<=1;i++){//0为装入1位不装入
13           if(wei-w[k]*i>=0){//如果还有剩余空间,实现了剪枝
14             bag[k]=i;//记录该物品是否被装入
15             count1=count1+v[k]*i;//总价值
16             if(k==N && count1 >best){//此时装载方案是目前已知的装载方案最优
17                 best=count1;//更新这个最优总价值
18                 for(int j=1;j<=N;j++){//记录此时背包装入状态
19                     y[j]=bag[j];
20                 }
21             }
22             if(k<N){//k==n递归
23                 procedure(k+1,wei-w[k]*i,N);
24             }
25 
26             count1-=v[k]*i;//k<n回溯上一步
27           }
28     }
29 }
30 int main()
31 {
32         memset(v,0,sizeof(v));
33         memset(bag,0,sizeof(bag));
34         memset(y,0,sizeof(y));
35         memset(w,0,sizeof(w));
36         cout << "请输入物品的总个数(n<=9)" << endl;
37         int n;
38         cin >> n;
39         cout << "请输入每个物品的重量" << endl;
40         for(int i=1;i<=n;i++){
41             cin >> w[i];
42         }
43          cout << "请输入每个物品的价值" << endl;
44         for(int i=1;i<=n;i++){
45             cin >> v[i];
46         }
47         cout << "请输入该背包最多可以装入的物品的总重量" << endl;
48         int wei;
49         cin >> wei;
50            procedure(0,wei,n);
51         cout <<"该背包可以装入的最大物品总价值是" << endl;
52         cout << best << endl;
53         cout << "装入的物品有" << endl;
54         for(int i=1;i<=n;i++){
55                if(y[i]==1){
56                 cout << "物品" << i << " ";
57                }
58         }
59 }