440. Backpack III （和Backpack II的区别就是，这里元素可重复利用，而II不可重复利用）

Description

中文English

Given n kinds of items, and each kind of item has an infinite number available. The i-thitem has size A[i] and value V[i].

Also given a backpack with size m. What is the maximum value you can put into the backpack?

1. You cannot divide item into small pieces.
2. Total size of items you put into backpack can not exceed m.

Have you met this question in a real interview?  

Example

Example 1:

Input: A = [2, 3, 5, 7], V = [1, 5, 2, 4], m = 10
Output: 15
Explanation: Put three item 1 (A[1] = 3, V[1] = 5) into backpack.

Example 2:

Input: A = [1, 2, 3], V = [1, 2, 3], m = 5
Output: 5
Explanation: Strategy is not unique. For example, put five item 0 (A[0] = 1, V[0] = 1) into backpack.

class Solution { public: /** * @param A: an integer array * @param V: an integer array * @param m: An integer * @return: an array */ int backPackIII(vector<int> &A, vector<int> &V, int m) { // write your code here vector<int> dp(m + 1, 0); for(int i = 0; i < A.size(); i++){ for(int j = A[i]; j <= m; j++){ dp[j] = max(dp[j - A[i]] + V[i], dp[j]); } } return dp[m]; } };