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.
Constraints
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)
