算法試卷第五題，看了下，根據(jù)題意對(duì)答案進(jìn)行了一下擴(kuò)展，用C++把算法寫(xiě)了下。哎，不早了，該睡覺(jué)了。
題目：
5、（0-1背包問(wèn)題）現(xiàn)有五個(gè)物品，其中（w1,w2,w3,w4,w5=(3,4,7,8,9),(v1,v2,v3,v4,v5)=(4,5,10,11,13)，W=17.(wi表示物品重量，vi表示物品價(jià)值，W表示背包所能承受的總重量)。求背包能獲得最大價(jià)值的裝法
1
#include <stdio.h>
2#include <vector>
3#include <iostream.h>
4using namespace std;
5int knapsack(vector<double> w, vector<double> v,int W)
6
{
7
int i=w.size();
8 double *arg=new double[i]; //物品的單位重量?jī)r(jià)值
9 //算出各物品的單位重量?jī)r(jià)值
10
for(int j=0;j<i;j++){
11 arg[j]=v[j]/w[j];
12
}
13 int *rank=new int[i];
14 for(int k=0;k<i;k++){//賦初始值，順序與物品下標(biāo)相同
15 rank[k]=k;
16 }
17
18 for(int m=0;m<i;m++){
19
20 for(int n=m;n<i;n++){
21 if(arg[m]<arg[n]){
22 double t;
23 //轉(zhuǎn)換值
24 t=arg[m];
25 arg[m]=arg[n];
26 arg[n]=t;
27 //轉(zhuǎn)換下標(biāo)
28 int temp1=rank[m];
29 int temp2=rank[n];
30 rank[m]=temp2;
31 rank[n]=temp1;
32 }
33 }
34 }
35 int *x=new int[i];//存放各物品放在包里的數(shù)量x[1]則為第二件物品放在包里的數(shù)量
36 for(int z=0;z<i;z++){
37 if(W/w[rank[z]]==0)continue;//判斷是否能翻進(jìn)去 為0則說(shuō)明當(dāng)前物品超重
38 x[rank[z]]=W/w[rank[z]];//計(jì)算可以存放的物品數(shù)量
39 W=W-(W/w[rank[z]])*w[rank[z]];
40 }
41 cout<<"[";
42 for(int y=0;y<i;y++){
43 cout <<"x"<<y+1;
44 if(y+1!=i)cout <<",";
45 }
46 cout <<"]=";
47 cout <<"[";
48 for(y=0;y<i;y++){
49 cout <<x[y];
50 if(y+1!=i)cout <<",";
51 }
52 cout <<"]";
53 delete rank;
54 delete x;
55 delete arg;
56return 0;
57
}
58