原题

LintCode 125. Backpack II

Description

Given n items with size Ai and value Vi, and a backpack with size m. What's the maximum value can you put into the backpack?

Notice

You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.

Example

Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9.

解题

这道题可以说和LintCode 92. Backpack没有任何区别，只不过LintCode 92. Backpack商品的价值和自身的体积是样的，而这里价值有另外一个表。略作修改即可通过。

代码

class Solution {
public:
    /*
    * @param m: An integer m denotes the size of a backpack
    * @param A: Given n items with size A[i]
    * @param V: Given n items with value V[i]
    * @return: The maximum value
    */
    int backPackII(int m, vector<int> &A, vector<int> &V) {
        // write your code here
        vector<int> vec(m + 1);
        for (int i = 0; i < A.size(); i++) {
            for (int j = m; j > 0; j--) {
                if (j >= A[i]) {
                    vec[j] = max(vec[j], vec[j - A[i]] + V[i]);
                }
            }
        }
        return vec.back();
    }
};