背包问题

引入

简介：背包问题是一个经典的 组合优化问题，用于描述在给定的背包容量下如何选择物品以使得其价值最大化。通常情况下，背包问题可以分为 0-1 背包问题 和 分数背包问题 两种，其他还有 完全背包问题，分组背包问题。

解决方法：常见的解决方法有动态规划、贪心算法和回溯算法等。其中，动态规划是解决这类问题的主流方法之一，其时间复杂度相对较低。

0-1 背包

例题：

题意概要：有 n 种物品和一个容量为 W 的背包，每种物品有重量 和价值 两种属性并且每种物品只有一个，要求选若干个物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

Code:

const int N=1e5+10;
int n,W,w[N],v[N];
long long dp[100*N];
void solve()
{
    cin>>W>>n;
    for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++){
        for(int j=W;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    cout<<dp[W]<<endl;
}

分析：

建立状态表示 dp[i][j]: 从前 i 个物品选择放入容量为 j 的背包中的最大价值。

二维动态规划状态转移方程：

一维动态规划状态转移方程：