01背包问题C++

原题链接：https://www.acwing.com/problem/content/2/
算法标签：01背包 动态规划
分析过程：
一、确定方程状态：dp[i][j]表示处理完第i件物品（不取或取），背包容积为j时所获取的最大价值
二、建立状态转移方程：dp[i][j] = max( dp[i-1][j], dp[i-1][j-v[i]] w[i] )
三、考虑初始状态
法一：经典01背包解法

#include<iostream>
#include<algorithm>
using namespace std;
int dp[1009][1009];
int main(){
	int n, m;
	int v[1009], w[1009];
	cin >> n >> m;
	for( int i=1; i<=n; i   ){
		cin >> v[i] >> w[i];
	}
	for( int i=1; i<=n; i   ){
		for( int j=v[i]; j<=m; j   ){
			dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]   w[i]);
		}
	}
	cout << dp[n][m];
	return 0;
}

法二：空间优化
根据样例分析，绘制表格如下：

对于dp[i][j]，不取第i件物品时的 dp[i-1][j] 来自该列的上一行的表格值，取第i件物品时的 dp[i-1][j-v[i]] w[i] 来自上一行的左边部分的表格值，所以说，对于优化后的状态转移方程：dp[j] = max(dp[j], dp[j-v[i]] w[i])，如果内层循环是 int j=v[i]->m 的话，dp[j] 会覆盖原来的值，状态转移方程里的 dp[j-v[i]] 就来自当前行。相反，如果将循环改为 int j=m->v[i]，每次计算 dp[j] 时用到的数据都是来自上一次的数据，刚好符合我们的计算规则。

#include<iostream>
#include<algorithm>
using namespace std;
int dp[1009];
int main(){
	int n, m;
	int v[1009], w[1009];
	cin >> n >> m;
	for( int i=1; i<=n; i   ){
		cin >> v[i] >> w[i];
	}
	for( int i=1; i<=n; i   ){
		for( int j=m; j>=v[i]; j-- ){
			dp[j] = max(dp[j], dp[j-v[i]]   w[i]);
		}
	}
	cout << dp[m];
	return 0;
}

这篇好文章是转载于：学新通技术网