Submission #1286438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286438		ankit94	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	568 KiB

knapsack

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

int t[2005][2005];

int knapsack(int s, int n, vector<int>& V, vector<int>& W, vector<int>& K) {
    // we have 2 choices
    // Base case  -- smallest possible input
    if(n == 0 || s == 0) return 0;

    if(t[n][s] != -1) return t[n][s];

    if (W[n - 1] > s) return t[n][s] = knapsack(s, n - 1, V, W, K);

    int ans = knapsack(s, n-1, V, W, K);

    for(int i=1;i<=K[n-1];i++) {
        if(i*W[n-1] <= s) {
            // we have choices
            ans = max(i*V[n-1] + knapsack(s-i*W[n-1], n-1, V, W, K), ans);
        } else break;
    }
    return t[n][s] = ans;
}

int main() {
    int S;  // capacity
    int N;

    cin>>S >>N;

    vector<int> V(N);
    vector<int> W(N);
    vector<int> K(N);  // it is copies

    for(int i=0;i<N;i++) {
        cin>>V[i] >>W[i]>>K[i];

    }
    // now , we have to return 
    cout<< knapsack(S, N, V, W, K) <<endl;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27