算法试卷第五题，看了下，根据题意对答案进行了一下扩展，用C++把算法写了下。哎，不早了，该睡觉了。
题目：
5、（0-1背包问题）现有五个物品，其中（w1,w2,w3,w4,w5=(3,4,7,8,9),(v1,v2,v3,v4,v5)=(4,5,10,11,13)，W=17.(wi表示物品重量，vi表示物品价值，W表示背包所能承受的总重量)。求背包能获得最大价值的装法
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]; //物品的单位重量价值
9 //算出各物品的单位重量价值
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++){//赋初始值，顺序与物品下标相同
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 //转换值
24 t=arg[m];
25 arg[m]=arg[n];
26 arg[n]=t;
27 //转换下标
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];//存放各物品放在包里的数量x[1]则为第二件物品放在包里的数量
36 for(int z=0;z<i;z++){
37 if(W/w[rank[z]]==0)continue;//判断是否能翻进去 为0则说明当前物品超重
38 x[rank[z]]=W/w[rank[z]];//计算可以存放的物品数量
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