dp.cpp

//
//  main.cpp
//  DP
//
//  Created by oskimura on 2017/09/30.
//  Copyright (c) 2017年 oskimura. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

int main(int argc, const char * argv[]) {
    const char *filename = "/Users/osamukimura/work/tasks/tasks_365242days.txt";
    FILE *fh;
    
    auto maxDays = 365242;
    
    if ((fh = fopen(filename,"r")) == NULL) {
        printf("can't open");
        return -1;
    }

    char *t1, *t2;
    t1 = new char[32];
    t2 = new char[32];
    
    fscanf(fh, "%s\t%s", &t1,&t2);
    
    int day;
    int wadge;
    std::vector<int> days;
    std::vector<int> wadges;
    
    int count = 0;
    while(fscanf(fh, "%d\t%d",&day,&wadge)!=EOF) {
        days.push_back(day);
        wadges.push_back(wadge);
        count++;
    }
    fclose(fh);
    std::vector<std::vector<int>> dp(count+1,std::vector<int>(maxDays+1));
    
    //[maxDays+1]
    //dp[0] = new int[(count+1) * (maxDays+1)];
    
    /*
    
    for (int i=0;i<count;i++) {
        dp[i] = new int[maxDays+1];
    }
    */
    
    for (int i=0;i<maxDays;i++) {
        dp[count][i] = 0;
    }
    
    for (int i=count-1;i>=0;i--) {
        for (int j=0;j<=maxDays;j++) {
            if (j<days[i]) {
                dp[i][j] = dp[i+1][j];
            }
            else {
                dp[i][j] =
                std::max(dp[i+1][j], dp[i+1][j-days[i]] + wadges[i]);
            }
        }
        
    }
    
    printf("%d\n",dp[0][maxDays]);
    return 0;
}