Knapsack

#include <iostream>
#include <vector>
using namespace std;
#define max(x,y) ((x<y) ? y : x)

int main(){
    cin.tie(0); short n,k,i,j, z, batas;
    vector<int> v; // untuk menyimpan ouput
    cin >> n >> k; // input
    short berat[k+1],harga[k+1],arr[k+1][n+1];
    berat[0]=harga[0]=0; //awal berat & harga di set ke 0, karna idx yg dipakai dari 1
    for (i=1;i<=k;i++) cin >> berat[i] >> harga[i];

    //reference YT Abdul Bari
    for (i=0;i<=k;i++){
        for(j=0;j <=n;j++){
            if(j==0 || i==0) arr[i][j]=0;
            else if (berat[i] <= j) arr[i][j] = max(harga[i] + arr[i-1][j-berat[i]], arr[i-1][j]);
            else arr[i][j] = arr[i-1][j];
        }
    }
    j=n; // mencari j terkecil yg bernilai = arr[k][n]
    while(arr[k][j]== arr[k][n]) j--;
    j++;

    for(i = k ;i>0 && j > 0; i--){  // loop mencari jumlah cara pengambilan batu
        // cout <<"\n" << i << " " << j << " " << arr[i][j] << " " << arr[i-1][j];
        if(arr[i][j]==arr[i-1][j]) continue;
        else{
            v.push_back(i);
            j -= berat[i];
            // cout <<"\n"<< i << " " <<j;
        }
    }// di cetak dari belakang
    for(i = v.size()-1 ; i >= 0; i--) cout << v[i] << endl;
    return 0;
}