[特殊字符] 背包问题详解（0/1 背包、完全背包、多重背包）—

🧳 背包问题详解（0/1 背包、完全背包、多重背包）——附 C++ 实现

一、什么是背包问题？

背包问题（Knapsack Problem）是经典的动态规划问题之一：

给定一个容量有限的背包和若干物品，每个物品有体积（或重量）*和*价值，问如何选择物品使得总价值最大**。

根据每个物品可选次数不同，背包问题主要分为：

0/1 背包（每个物品最多选一次）
完全背包（每个物品可以选无限次）
多重背包（每个物品有固定数量）

二、0/1 背包问题

1️⃣ 问题描述

背包容量：W
物品数量：n
第i个物品：
- 重量：w[i]
- 价值：v[i]
每个物品最多选一次

目标：
👉 在不超过背包容量的前提下，使总价值最大。

2️⃣ 状态定义

令：

dp[j] = 容量为 j 时能获得的最大价值

3️⃣ 状态转移方程

对于第i个物品：

dp[j] = max(dp[j], dp[j - w[i]] + v[i])

⚠️关键点：
j必须从大到小遍历，防止一个物品被选多次。

4️⃣ C++ 实现（0/1 背包）

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,W;cin>>n>>W;vector<int>w(n),v(n);for(inti=0;i<n;i++){cin>>w[i]>>v[i];}vector<int>dp(W+1,0);for(inti=0;i<n;i++){for(intj=W;j>=w[i];j--){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}cout<<dp[W]<<endl;return0;}

三、完全背包问题

1️⃣ 问题描述

与 0/1 背包类似，但：

每个物品可以选无限次

2️⃣ 状态转移区别

dp[j] = max(dp[j], dp[j - w[i]] + v[i])

⚠️关键区别：
j必须从小到大遍历，允许多次使用当前物品。

3️⃣ C++ 实现（完全背包）

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,W;cin>>n>>W;vector<int>w(n),v(n);for(inti=0;i<n;i++){cin>>w[i]>>v[i];}vector<int>dp(W+1,0);for(inti=0;i<n;i++){for(intj=w[i];j<=W;j++){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}cout<<dp[W]<<endl;return0;}

四、多重背包问题

1️⃣ 问题描述

每个物品最多只能选k[i]次

2️⃣ 常见解决方法

✅ 方法一：暴力枚举（不推荐）

三重循环，时间复杂度高。

✅ 方法二：二进制拆分（推荐）

将k个物品拆成：

1, 2, 4, ..., 剩余

然后转化为0/1 背包问题。

3️⃣ C++ 实现（二进制优化）

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,W;cin>>n>>W;vector<int>dp(W+1,0);for(inti=0;i<n;i++){intw,v,k;cin>>w>>v>>k;for(intc=1;k>0;c<<=1){intnum=min(c,k);k-=num;intweight=num*w;intvalue=num*v;for(intj=W;j>=weight;j--){dp[j]=max(dp[j],dp[j-weight]+value);}}}cout<<dp[W]<<endl;return0;}