kanpsak in dynamic programming

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;
vector<string>V;
vector<int>Vi;
int dp[100][100];
int os[100][100];
void print(int K,int n,int w[]);
int knapsak(int n,int w[],int v[],int W)
{
    int i,j;
    for(i=0;i<=n;i++)
        dp[i][0]=0;
    for(i=0;i<=W;i++)
        dp[0][i]=0;

    for(i=1;i<=n;i++)
    {
        for(j=0;j<=W;j++)
        {
            if(j-w[i]>=0&&v[i]+dp[i-1][j-w[i]]>dp[i-1][j])
            {
                dp[i][j]=v[i]+dp[i-1][j-w[i]];
                os[i][j]=1;

            }
            else
            {
                dp[i][j]=dp[i-1][j];
                os[i][j]=0;
            }

        }

    }
    print(W,n,w);

return dp[n][W];



}

void print(int K,int n,int w[])
{

    for(int i=n;i>=1;i--)
    {

        if(os[i][K]==1)
        {
            Vi.push_back(i);
            K=K-w[i];
        }
    }
}
int main()
{


    freopen("in.txt","r",stdin);
    int n,W,w[100],v[100];
    char str[1000];
    string temp1,temp2;
    cin>>temp1>>temp2;

    scanf("%d",&W);
    int i=1;
    char ch[100];
    getchar();
    V.push_back("NULL");
    while(cin>>str)
    {
       if(str[0]=='\n') break;
       V.push_back(str);
       cin>>v[i]>>w[i];
       getchar();

       i++;

    }


    int ans=knapsak(i,w,v,W);
    cout<<"Number of criminals: "<<ans<<endl;
    cout<<"Files taken: ";
    for(int i=Vi.size()-1;i>=0;i--)
    {
        cout<<V[Vi[i]]<<" ";
    }
    cout<<endl;


}

input:
 USB SIZE 10
file1 10 5
file2 40 4
file3 30 6
file4 50 3
output:
90
file2 file4

SHARE

Amit Ghosh

• 
• 
• 
• 
•