Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

AtCoder Beginner Contest 060 D - Simple Knapsack

Problem Statement

You have N items and a bag of strength W. The i-th item has a weight of wi and a value of vi.

You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.

Your objective is to maximize the total value of the selected items.


1≤N≤100 1≤W≤109 1≤wi≤109 For each i=2,3,…,N, w1≤wi≤w1+3. 1≤vi≤107 W, each wi and vi are integers.

how to solve

We have to check the constraints. In this problem w and v is big, so we cannot solve this problem in common dynamic programming way. This time we use the constraint w1 ≤ wi ≤ w1 + 3. Because of this, there are at most 4 possible weights for a single item. So I can test the all case that is how many items I have to use per 4 weights. This time complexity is O(n4)

code is following