背包DP

1.01背包

01背包其实就是一个物品只能选一次，for的i循环正序，j循环倒序

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+5;
int v,n;
int c[N],w[N],dp[N];
signed main(){
	cin>>v>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>c[i]; 
	}
	for(int i=1;i<=n;i++){
		for(int j=v;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
			//cout<<dp[i][j]<<" ";
		}
	}
	cout<<dp[v];
	return 0;
}

---

2.怎么做

1.划分界限：

做前先使用双脑想一下是否满足动态规划的条件

2. 定义状态：

用变量描述问题的子结构（如 dp[i] 表示第 i 个阶段的最优解）

3.状态转移方程

建立子问题间的递推关系（如 dp[j]=max(dp[j],dp[j-w[i]]+c[i])）dxd说这是重点。(max里的dp[j]是不选)

4.初始化与边界

设置初始值（如 dp[0] = 0, dp[1] = 1）

5.输出结果

从最终状态回溯或直接获取解（如 dp[n] 为所求）

2.完全背包

完全背包其实就是一个物品不限数量的选，for的i，j都是正序

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+5;
int v,n;
int c[N],w[N],dp[N];
signed main(){
	cin>>v>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>c[i]; 
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=v;j++){
			if(j-w[i]>=0)
			dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
			//cout<<dp[i][j]<<" ";
		}
	}
	cout<<dp[v];
	return 0;
}

---

2.怎么做

1.划分界限：

做前先使用双脑想一下是否满足动态规划的条件

2. 定义状态：

用变量描述问题的子结构（如 dp[i] 表示第 i 个阶段的最优解）

3.状态转移方程

建立子问题间的递推关系（如 dp[j]=max(dp[j],dp[j-w[i]]+c[i])）dxd说这是重点。(max里的dp[j]是不选)

4.初始化与边界

设置初始值（如 dp[0] = 0, dp[1] = 1）

5.输出结果

从最终状态回溯或直接获取解（如 dp[n] 为所求）