01背包问题

问题描述

有N件物品和一个容量为V的背包。第i件物品的价值是c[i]，重量是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。每种物品只有一件，可以选择放或者不放。

思路

首先定义状态转移方程dp[i] [j]为在容量为j的背包中放入前i件物品，所具有的最大价值。

当背包足够装下某一个物品时，对于这个物品都有放与不放两种状态，对应的状态转移方程为：

$$dp[i][j]=max(dp[i-1][j-w[i]]+c[i],dp[i-1][j]$$

code

#include <iostream>

using namespace std;

int n,v,c[1000000],w[1000000];
int dp[105][1005];
int main()
{
    cin >> v >> n;
    for(int i=1; i<=n; i++)
        cin >> c[i] >> w[i];
    

    for(int i=1; i<=n; i++) //物品 
        for(int j=v; j>=0; j--) //容量 
        {
            if(j >= w[i]) //当背包剩余容量大于此物品时 
                dp[i][j] = max(dp[i-1][j-w[i]]+c[i], dp[i-1][j]);
            else      //当背包剩余容量小于此物品时
                dp[i][j] = dp[i-1][j];           
        }
    cout << dp[n][v] << endl;
    return 0;

}

打赏