0-1背包问题

问题描述

• 现有一个容量大小为V的背包和N件物品，每件物品有两个属性，体积和价值，请问这个背包最多能装价值为多少的物品？

输入描述

• 第一行两个整数V和n。接下来n行，每行两个整数体积和价值。1≤N≤1000,1≤V≤20000。每件物品的体积和价值范围在[1,500]。

输出描述

• 输出背包最多能装的物品价值。
• 示例：
  6 3
  3 5
  2 4
  4 2
  输出
  9

思路

• 分两种情况， 一种是放不放的下选择，一种是放不放的问题

代码实现

int test(std::vector<int>& A, std::vector<int>& V, int pack) {
    int row = A.size();
    int col = pack;

    std::vector<std::vector<int>> dp(row+1, std::vector<int>(col+1, 0));

    for(int i = 1; i <= row; ++i) {
        for(int j = 1; j <= col; ++j) {
            if(j < A[i-1]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = std::max(dp[i-1][j], dp[i-A[i-1]]+V[i-1]);
            }
        }
    }

    return dp[row][col];
}





int main()
{
    int pack, num;
    while(std::cin >> pack >> num) {
        std::vector<int> A(num);
        std::vector<int> V(num);

        for(int i = 0; i < num; ++i) {
            std::cin >> A[i] >> V[i];
        }

        std::cout << test(A, V, pack) << std::endl;
    }
    return 0;
}

// 一维空间优化
int test(std::vector<int>& A, std::vector<int>& V, int pack) {
    std::vector<int> dp(pack+1, 0);

    for(int i = 0; i < A.size(); ++i) {
        for(int j = pack; j >= A[i]; --j) {
            dp[j] = std::max(dp[j], dp[j-A[i]]+V[i]);
        }
    }

    return dp[pack];
}