华为机试——0-1背包问题

华为机试——0-1背包问题

给定一个数，比如20，然后给定几个数字，如1 3 5 7 8

输出：

1 3 5 7 8

0 0 0 1 1

因为5+7+8=20

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int number,tmp,max=0,index;
    vector<int> num;
    vector<int> count;
    int total_number=0;
    cin>>number;
    while(cin>>tmp)
        num.push_back(tmp);
    int length=num.size();
    for(int i=0;i<length;i++)
        count.push_back(0);
//  sort(num.begin(),num.end(),greater<int>());
    while(total_number <= number)
    {
        if(total_number == number)
            break;
        for(int i=0;i<length;i++)
        {
            if(num[i]>max && count[i]==0)
            {
                max=num[i];
                index=i;
            }
        }
        total_number += max;
        ++count[index];
        max=0;

    }
    for(int i=0;i<length;i++)
        cout<<num[i]<<" ";
    cout<<endl;
    for(int i=0;i<length;i++)
        cout<<count[i]<<"  ";
    cout<<endl;
}