AOJ

# # Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B

# # Computetional complexity

$O(NW)$

where N is the number of items and W is the capacity

# # Solution


#define V_MAX 1000
#define W_MAX 1000
#define N_MAX 100
#define CAP_MAX 10000
#define W_INF 1001

struct Item { Int value, weight; };

Int N, CAP;
vector<Item> items;
Int dp[CAP_MAX+1][N_MAX+1];

Int solve() {
loop(n,0,N+1) {
dp[0][n] = 0;
}

loop(cap,0,CAP+1) {
dp[cap][0] = 0;
}

loop(n,1,N+1) {
Item item = items[n];
loop(cap,1,CAP+1) {
if (item.weight > cap) continue;
dp[cap][n] = max(dp[cap][n-1], dp[cap-item.weight][n-1] + item.value);
}
}
return dp[CAP][N];
}

int main(void) {
Int v, w;
cin >> N >> CAP;
items.push_back({0, W_INF}); // dummy
while (cin >> v >> w) {
items.push_back({ v, w });
}

cout << solve() << endl;
return 0;
}


Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!