2.01 backpack problem

subject ：

Yes N Items and a capacity are V The backpack . Each item can only be used once .

The first i The volume of the item is vi, The value is wi.

Find out which items to pack in your backpack , The total volume of these items can not exceed the capacity of the backpack , And the total value is the greatest .
Output maximum value .

Input format ：

The first line has two integers ,N,V, Space off , They are the number of items and the volume of the backpack .

Next there is N That's ok , Two integers per line vi,wi, Space off , Separate indication control i The volume and value of items .

Output format ：

Output an integer , Represents the greatest value .

Data range ：

sample input ：

4 5
1 2
2 4
3 4
4 5

sample output ：

8

Ideas ：

Solution one code ：

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1100;

int n,m;
int f[N][N],v[N],w[N];

int main()
{
    
    cin>>n>>m;

    for(int i = 1;i<=n;i++)cin>>v[i]>>w[i];

    for(int i = 1;i<=n;i++) 
     for(int j= 0;j<=m;j++)
     {
    
         f[i][j] = f[i-1][j];
         if(j >= v[i] )  f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i]);
     }

     cout<<f[n][m]<<endl;
    return 0;
}

Solution II code ：（ Optimized one-dimensional approach ）

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1100;

int n,m;
int f[N],v[N],w[N];

int main()
{
    
    cin>>n>>m;

    for(int i = 1;i<=n;i++)cin>>v[i]>>w[i];

    for(int i = 1;i<=n;i++) 
     for(int j=m;j>=v[i];j--)
     {
    
           f[j] = max(f[j],f[j-v[i]] + w[i]);
     }

     cout<<f[m]<<endl;
    return 0;
}