DPL_1_B 0-1 Knapsack problem

Calendar Clock iconCalendar Clock icon

AOJ

Table of contents

# Problem

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

# Computetional complexity

O(NW)O(NW)

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

# Solution

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#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!

Comments