anonymous ナップサック問題書き直し
No License C++
2019年05月20日
Copy Clone
#include <iostream>
#include <algorithm>
using namespace std;

const int n=6, W=8;
const int w[n] = {2,1,3,2,1,5}, v[n]={3,2,6,1,3,85};

int dp[10][10];

int rec(int i, int cap) {
    if (dp[i][cap] != -1) {
        return dp[i][cap];
    }

    int res;
    if (i == n) {
        res = 0;
    } else if (cap < w[i]) {
        res = rec(i + 1, cap);
    } else {
        res = max(
            rec(i + 1, cap),
            rec(i + 1, cap - w[i]) + v[i]
        );
    }
    return dp[i][cap] = res;
}

int main() {
    memset(dp, -1, sizeof(dp));
    cout << rec(0, W) << endl;
}
#include <iostream>
#include <algorithm>
using namespace std;

const int n=6, W=8;
const int w[n] = {2,1,3,2,1,5}, v[n]={3,2,6,1,3,85};

int dp[10][10];

int rec(int i, int cap) {
    if (dp[i][cap] != -1) {
        return dp[i][cap];
    }

    int res;
    if (i == n) {
        res = 0;
    } else if (cap < w[i]) {
        res = rec(i + 1, cap);
    } else {
        res = max(
            rec(i + 1, cap),
            rec(i + 1, cap - w[i]) + v[i]
        );
    }
    return dp[i][cap] = res;
}

int main() {
    memset(dp, -1, sizeof(dp));
    cout << rec(0, W) << endl;
}
anonymous
Anonymous
2019年05月21日
メモ化するやつね
Bot
Bot
2019年05月25日
#include <iostream> #include <algorithm> using namespace std; const int n=6, W=8; const int w[n] = {2,1,3,2,1,5}, v[n]={3,2,6,1,3,85}; int dp[10][10]; int rec(int i, int cap) { if (dp[i][cap] != -1) { return dp[i][cap]; } int res; if (i == n) { res = 0; } else if (cap < w[i]) { res = rec(i + 1, cap); } else { res = max( rec(i + 1, cap), rec(i + 1, cap - w[i]) + v[i] ); } return dp[i][cap] = res; } int main() { memset(dp, -1, sizeof(dp)); cout << rec(0, W) << endl; }
Bot
Bot
2019年05月26日
#include <iostream> #include <algorithm> using namespace std; const int n=6, W=8; const int w[n] = {2,1,3,2,1,5}, v[n]={3,2,6,1,3,85}; int dp[10][10]; int rec(int i, int cap) { if (dp[i][cap] != -1) { return dp[i][cap]; } int res; if (i == n) { res = 0; } else if (cap < w[i]) { res = rec(i + 1, cap); } else { res = max( rec(i + 1, cap), rec(i + 1, cap - w[i]) + v[i] ); } return dp[i][cap] = res; } int main() { memset(dp, -1, sizeof(dp)); cout << rec(0, W) << endl; }
anonymous
Anonymous
2019年06月01日
コメントテスト
anonymous
Anonymous
2019年06月08日
コメント