Simple knapsack problem

Title Description :

Given n An item and a backpack . goods ***i*** Weight of （ Volume ） yes ***wi***, Its value is ***vi***, The capacity of the backpack is ***C***. ask ： How to choose the items to load in the backpack , To maximize the total value of items in a backpack .

Another form of description ：

Ideas

An optimization problem , How to solve it ？

The easiest thing to think of is Enumeration , namely ： Test all the options you can put into your backpack , See which is the most valuable . The scheme here refers to ： Which ones to choose Xi( goods ), Note that the total number of items selected and which one to choose are not fixed

Then there is num Items , How many possible solutions are there ？

Of course, choose or not choose each item 2 In this case ,N An object is $2^{Num}$ Kind of plan .

How to express each scheme ？

It can be expressed as a number Suppose there is 8 Items , The corresponding to the $0-127(2^8-1)$ All the numbers of . Why? ？

0 Written in binary = 0000 0000 Each person represents an object ,0 It's the choice ,1 No election .

for example 7 = 0000 0111 The representative selects the second 1 2 3 Items 1 0 0 0 0 1 1 1 For choice The first 1 2 3 8 Items

---

Then the pseudo code :

for (i=0 to $2^n-1$) {
take i The corresponding binary numbers are stored in the array by bits Y in ;
Try to follow the packaging scheme y Pack , Then the weight of the items in the backpack is CurWeight, Value is CurValue;
If CurWeight>C, Then discard the scheme , Continue to try the next solution ; otherwise , If the scheme is better than the previous scheme , That is, if CurValue>Value, The scheme is temporarily saved ： namely X=Y,Value=CurValue, Weight= CurWeight. Continue to cycle ;
}

It means from $i=0to{2}^{(n)}-1$ Traverse , every last i Split into binary to represent a number , Then you get a solution .

Traverse all items , Everyone will see if they have chosen , Calculate the total value and weight under the current scheme , Compared with and recorded , If it's better , Update the previous record .

The final output .

Be careful (W And V Are floating point numbers )

Code :( Do not directly Copy)

C++ edition :

#include<iostream>
#include<bits/stdc++.h>//  One C++ Library function   Don't have to 
using namespace std;
int main()
{
    int bag,num;
    cin>>bag>>num;// You can change to scanf
    vector<float> items(num+1,0);//
    vector<float> vals(num+1,0);
    for(int i=1;i<=num;i++){
        cin>>items[i];
    }
    for(int i=1;i<=num;i++){
        cin>>vals[i];
    }
    int best_i = 0;
    float ans = 0;
    float finalweight = 0;
    int N = pow(2,num)-1;
    for(int i=0;i<=N;i++){
        float curweight=0;
        float val = 0;
        int biti = i;
        for(int j=0;j<num;j++){
            if( (biti>>j)%2==1){
                // choose 
                curweight+=items[j+1];
                val+=vals[j+1];
                if(curweight > bag)
                    break;
            }
        }
        if(curweight <= bag)
            if(val > ans){
                ans = val;
                best_i = biti;
                finalweight = curweight;
            }
    }
    for(int i=0;i<num;i++){
        if((best_i>>i) %2 == 1) 
            cout<<i+1<<" ";
    }
    printf("%d %d",(int)finalweight,(int)ans);
    return 0;
}

C The language code :

#include<iostream>
#include<math.h>
const int MAXN = 100;
int main()
{
    int bag,num;
    float *items,*vals;
    scanf("%d%d",&bag,&num);
    
    // Dynamic application of one-dimensional array  
    items = (float*)malloc(4*(num+1));// Add 1 You can put it 0 no need 
    vals = (float*)malloc(4*(num+1));// Add 1 You can put it 0 no need 

    for(int i=1;i<=num;i++){
        scanf("%f",&items[i]);
    }
    for(int i=1;i<=num;i++){
        scanf("%f",&vals[i]);
    }

    int best_i = 0;//  Record the best plan   The binary representation of a number 
    float ans = 0; // ans For the final result , value 
    float finalweight = 0;// The final weight 
    int N = pow(2,num)-1;
    for(int i=0;i<=N;i++){
        float curweight=0;
        float val = 0;
        int biti = i;//  Copy 
        for(int j=0;j<num;j++){
            if( (biti>>j)%2==1){
                // This bit operation is   hold biti( Written in binary ) Moves to the right one  
                // Look, after moving right   Is the lowest position 1  yes 1 Represents the current item j  Under this scheme, we choose 
                // choose 
                curweight+=items[j+1];
                val+=vals[j+1];
                if(curweight > bag)
                    break;
            }
        }
        if(curweight <= bag)
            if(val > ans){
                ans = val;
                best_i = biti;
                finalweight = curweight;
            }
    }
    for(int i=0;i<num;i++){
        if((best_i>>i) %2 == 1) 
            printf("%d ",i+1);
    }
    printf("%d %d",(int)finalweight,(int)ans);
    return 0;
}