U239190 背包问题
题目背景
# 01背包
**题目：** 有一个背包，容量为$n$，有$m$个物品，每个物品$i$体积为$w[i]$，价值为$v[i]$，数量为$1$。求背包装的下的物品的最大价值总和。
## 思路
**~~错误思路：贪心（每次拿单位价值高的物品）~~**
### 正确思路 ：动态规划（DP）$★$
$★$ **状态定义：$dp[i][j]$表示在背包容量限制为j时处理完前i个物品的最大值。**
---
## 问题分解：第$i$件物品要么装入，要么不装入。
**当$j=w[i]$**：
### 装入：$dp[i][j]=dp[i-1][j-w[i]]+v[i]★$。
### 不装：$dp[i][j]=dp[i-1][j]$。
### 整合：$dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j])$
---
## 代码
```cpp
#include
using namespace std;
int dp[205][205],w[35],v[35];
int main(){
int c,n;
cin >> c >> n;
for (int i = 1;i > w[i] >> v[i];
}
for (int i = 1;i > n;
for (int i = 1;i > w[i] >> v[i];
}
for (int i = 1;i = w[i];j--){
dp[j] = max(dp[j - w[i]] + v[i],dp[j]);
}
}
cout
题目描述
# 完全背包
**题目：** 有一个背包，容量为$n$，有$m$个物品，每个物品$i$体积为$w[i]$，价值为$v[i]$，都有无限件。求背包装的下的物品的最大价值总和。
## 思路
**~~错误思路：贪心（每次拿单位价值高的物品）~~**
### 正确思路 ：动态规划（DP）$★$
$★$**状态定义：$dp[i][j]$表示在背包容量限制为j时处理完前i个物品的最大值。**
---
### 状态转移方程：$dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j])$
---
## 代码
```cpp
#include
using namespace std;
long long dp[1000005],w[10005],v[10005];
int main(){
int c,n;
cin >> c >> n;
for (int i = 1;i > w[i] >> v[i];
}
for (int i = 1;i
输入格式
# 多重背包
```cpp
#include
using namespace std;
int dp[6005][6005];
int w[1005],v[1005],s[1005];
int n,W;
int main(){
cin >> n >> W;
for (int i = 1;i > w[i] >> v[i] >> s[i];
for (int i = 1;i
输出格式
无