Задача о рюкзаке (0/1)

W = int(input())  # вместимость рюкзака
n = int(input())  # количество предметов
w = [0] * (n + 1)
c = [0] * (n + 1)

for i in range(1, n + 1):
    w[i] = int(input())
for i in range(1, n + 1):
    c[i] = int(input())

dp = [[0] * (W + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, W + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i])

print(dp[n][W])

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

int main() {
    int n, W;
    cin >> n >> W;
    
    vector<int> w(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    
    vector<int> c(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (j < w[i]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i]);
            }
        }
    }
    
    cout << dp[n][W];
    return 0;
}

W = int(input())  # вместимость рюкзака
n = int(input())  # количество предметов
A = [int(input()) for _ in range(n)]  # веса предметов

dp = [[0] * (W + 1) for _ in range(n + 1)]
dp[0][0] = 1

for i in range(1, n + 1):
    for j in range(W + 1):
        if A[i - 1] <= j:
            dp[i][j] = dp[i - 1][j] or dp[i - 1][j - A[i - 1]]
        else:
            dp[i][j] = dp[i - 1][j]

if dp[n][W] == 0:
    print(0)
    exit()

Z = []
i, j = n, W
while i != 0 or j != 0:
    if dp[i - 1][j] == 1 and (j >= A[i - 1] and dp[i - 1][j - A[i - 1]] == 1):
        print(-1)
        exit()
    else:
        if dp[i - 1][j] == 1:
            i -= 1
        else:
            i -= 1
            j -= A[i]
            Z.append(i + 1)

if len(Z) == 0:
    print(0)
else:
    print(*list(reversed(Z)))

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

int main() {
    int W, n;
    cin >> W >> n;
    
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    
    vector<vector<bool>> dp(n + 1, vector<bool>(W + 1, false));
    dp[0][0] = true;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            if (A[i - 1] <= j) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    
    if (!dp[n][W]) {
        cout << 0;
        return 0;
    }
    
    vector<int> Z;
    int i = n, j = W;
    while (i != 0 || j != 0) {
        if (dp[i - 1][j] && (j >= A[i - 1] && dp[i - 1][j - A[i - 1]])) {
            cout << -1;
            return 0;
        } else {
            if (dp[i - 1][j]) {
                i--;
            } else {
                i--;
                j -= A[i];
                Z.push_back(i + 1);
            }
        }
    }
    
    reverse(Z.begin(), Z.end());
    for (int x : Z) {
        cout << x << " ";
    }
    
    return 0;
}