背包

01 背包

\(n\) 件物品，每件物品有权值和重量，给出背包体积 \(V\)，从这些物品中挑选若干件（只能选一次）放入背包，使得背包内物品的总重量不超过 \(V\)，问能可以得到的最大权值。

设 \(dp[i][j]\) 选取前 \(i\) 件物品重量为 \(j\) 能取得的最大的权值，可以得到转移方程 \(dp[i][j]=max(dp[i-1][j-w[i]]+val[i],dp[i-1][j]);\)

因为 i 只与 i-1 有关所以考虑滚动数组：

交替滚动

用 now 表示现在的数组，用 old 表示上一个数组，交替使用。

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int t,m;
int w[202],val[202];
int dp[3][10010];

int main(){
	ios::sync_with_stdio(false);
	cin>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>w[i]>>val[i];
	}
	int now=0,old=1;
	for(int i=1;i<=m;i++){
		swap(old,now);
		for(int j=0;j<=t;j++){
			if(j>=w[i]){
				dp[now][j]=max(dp[old][j],dp[old][j-w[i]]+val[i]);
			}
			else{
				dp[now][j]=dp[old][j];
			}
		}
	}
	cout<<dp[now][t];
    return 0;
}

自我滚动

因为体积只会向小减少，所以从后向前遍历容量以确保每个数物品只选一次，上一次的数组储存的数（i-1） 结果全部就在这个数组里，这样空间压缩到一维。

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int t,m;
int w[202],val[202];
int dp[10010];

int main(){
	ios::sync_with_stdio(false);
	cin>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>w[i]>>val[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=t;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+val[i]);
		}
	}
	cout<<dp[t];
    return 0;
}

完全背包

\(n\) 件物品，每件物品有权值和重量，给出背包体积 \(V\)，从这些物品中挑选若干件（可以多次同选一个）放入背包，使得背包内物品的总重量不超过 \(V\)，问能可以得到的最大权值。

我们对 01 背包的代码进行更改为从小到大枚举容量，因为在计算某个容量时，可以确保之前计算的状态已经包含了该物品之前选择的次数，这样就能够正确地累积多个相同物品的价值。

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int t,m;
int w[202],val[202];
int dp[10010];

int main(){
	ios::sync_with_stdio(false);
	cin>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>w[i]>>val[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=w[i];j<=t;j++){
			dp[j]=max(dp[j],dp[j-w[i]]+val[i]);
		}
	}
	cout<<dp[t];
    return 0;
}