背包问题-贪心算法

1. 背包问题

给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? （说明，以下算法与教材147页给出的算法思想是一样的，教材上的算法事先对物品信息进行了排序）

代码如下：

#include "stdafx.h"

#include<stdio.h>

#include<iostream>

using namespace std;

const int num = 20;

void sort(int n,float v[num],float w[num]){

       int i,j;

       float t[num];

       for(i=1;i<=n;i++){

            t[i]=v[i]/w[i];

       }

       for(i=1;i<=n;i++){

              for(j=1;j<=n-i;j++){

                     if(t[j+1]<t[j]){


                            int m=v[j];

                            int n=w[j];

                            int k=t[j];

                            v[j]=v[j+1];

                            w[j]=w[j+1];

                            t[j]=t[j+1];

                            v[j+1]=m;

                            w[j+1]=n;

                            t[j+1]=k;

                     }
              }
       }

       cout<<"------------------------------------------------------------"<<endl;

       cout<<"物品           "<<"重量(w)          "<<"价值(v)       "<<"价值/重量(v/w)"<<endl;

       cout<<"------------------------------------------------------------"<<endl;

              for(i=1;i<=n;i++){

                     cout<<" "<<i<<"        "<<w[i]<<"         "<<v[i]<<"          "<<t[i];

                     cout<<endl;

              }

cout<<"------------------------------------------------------------"<<endl;
}

float Knapsack(int n, float C,float w[num],float v[num],float x[num]){

     int i;

       sort(n,v,w);

       for(i=1;i<=n;i++){

              x[i]=0;

       }

    i=1;

       int total=0;

       while(w[i]<C && i<=n){

         x[i] = 1;

         total = total+v[i];

         C=C-w[i];

         i++;

       }

       if(i<=n){

          x[i]= C/w[i];

          total = total+x[i]*v[i];

       }

       return total;

}

int main(int argc, char* argv[])

{

       int n;

       int i,j;

       float w[num];

       float v[num];

       float x[num];

       int C;

       cout<<"输入物品个数：";

       cin>>n;

       cout<<"输入物品重量："<<endl;

    for(i = 1;i<=n;i++){

              cin>>w[i];

       }

       cout<<"输入物品价值："<<endl;

    for(i = 1;i<=n;i++){

              cin>>v[i];

       }

       cout<<"输入背包的总重量：";

       cin>>C;

       int total= Knapsack(n,C,w,v,x);

       cout<<"贪心算法物品选择为：";

       for(i=1;i<=n;i++){

              cout<<x[i]<<"  ";

       }

       cout<<endl;

       cout<<"物品总价值为：";

       cout<<total;

       cout<<endl;

       return 0;
}

截图如下：