0-1 Knapsack

/// আমাকে ব্যাগের সাইজ m দেয়া আছে, আর n সংখ্যক জিনিসের দাম ও ওজন দেয়া আছে,
/// আমাকে এমন ভাবে জিনিস নিতে হবে,যাতে করে তাদের ওজন m এর বেশি না হয় আর দাম সবচেয়ে বেশি হয়।

#include<bits/stdc++.h>
using namespace std;

int w[2006];
int val[2006];

/// এখানে একটা জিনিস একাধিকবার নেয়া যাবে না। এজন্য 2d array লাগবে।
int profit[2004][2004];

int knap(int cap, int n)
{

/// i তম জিনিস পর্যন্ত j ওজন পর্যন্ত বেস্ট solution কোনটা |
///  মানে মোট কত কেজি জিনিস তার ব্যাগে নিতে পারব।
    for(int i= 0; i<=n; i++)
    {
        for(int j= 0; j<=cap; j++)
        {

/// প্রথম  j = 0 মানে কোন element নেয়া হয় নি।তাই ব্যাগেও কিছু নাই।
/// এখানে  i = 0, তার মানে এখনো কোন জিনিস নেয়া হয় নি, তাই ব্যাগে আছে ০ কেজি জিনিস।
            if(i == 0 || j== 0)
                profit[i][j]= 0;

            else if(w[i-1] <= j)
                profit[i][j]= max(val[i-1]+profit[i-1][j-w[i-1]], profit[i-1][j]);

            else
                profit[i][j]= profit[i-1][j];
        }
    }

    return profit[n][cap];
}


/// প্রথমে ধরব ব্যাগের ধারণক্ষমতা ১ কেজি। তখন সবচেয়ে বেশি লাভ কত, তা বের করব।
/// এই মান ব্যবহার করে বের করব, ব্যাগের ধারণক্ষমতা ২ কেজি হলে সবচেয়ে বেশি লাভ কত হবে।
/// এই মান ব্যাবহার করে বের করব, ব্যাগের ধারণক্ষমতা ৩ কেজি হলে সবচেয়ে বেশি লাভ কত হবে...
/// এভাবে একসময় ১ম element এর জন্য(আমাদের উদাহরণে স্বর্ণ) ব্যাগের ধারণক্ষমতা ১০ কেজি হলে সবচেয়ে বেশি লাভ কত হবে,তা বের হবে।
/// তারপর ২য় element নিয়ে কাজ করব।
/// এবার আবারো ব্যাগের ধারণক্ষমতা ১ কেজি হতে ১০ কেজি পর্যন্ত যাব,
/// আর চেক করব তখন এই ২য় element টা নিলে লাভ বেশি, নাকি না নিলে লাভ বেশি।
int main()
{

/// ব্যাগের ওজন দেয়া আছে s এ।
/// আর কয়টা জিনিস আছে, তা আছে n এ,
    int s,n;
    cin>>s>>n;

/// weight আছে weight[] array তে
/// জিনিসগুলোর দাম আছে values[] array তে
    for(int i=0; i<n; i++)
    {
        cin>>w[i]>>val[i];
    }

    cout<< knap(s,n) <<endl;
    return 0;
}

/// https://sites.google.com/site/programinggconcept/0-1-knapsack