01knapsack 더블릿 (복습 필요)

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int profit[300] = { 0 };
int weight[300] = { 0 };
int ans[300][11000] = { 0 };
 
int main() {
    int w, n;
    scanf("%d %d", &w, &n);
    getchar();
 
    for (int i = 1; i <= n; i++) {
        scanf("%d %d",&weight[i],&profit[i]);
    }
 
    for (int i = weight[1]; i <= w; i++) {
        ans[1][i] = profit[1];    
    }
    
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= w; j++) {
            if (j < weight[i]) {
                ans[i][j] = ans[i-1][j];                
            }
            else {
                ans[i][j] = max(ans[i - 1][j], 
                    profit[i] + ans[i - 1][j - weight[i]]);                
            }                    
        }                
    }
 
    printf("%d", ans[n][w]);
}