01背包问题(动态规划)

很多文章对dp的定义很模糊/不精准

有0->N-1个物品，v[i]为价值，w[i]为开销

状态描述：dp[i][j]为对0->i的物品分别进行购买/不购买的抉择，且至多使用j个背包空间，能获取的最大价值。

求取dp[i][j]时，需要利用dp[i-1][x]的值，对i物品进行抉择：如果w[i]>j，则意味着至多使用j个背包空间时无法容纳i物品，因此只能选择不购买，dp[i][j]=dp[i-1][j]。如果w[i]<=j，则意味着至多使用j个背包空间时可以容纳i物品，此时如果选择购买，则必须查看对0->i-1的物品抉择且至多使用j-w[i]的最大价值，dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j])

状态转移：dp[i][j]=max(dp[i-1][j-w[i]]+v[i](w[i]<=j),dp[i-1][j])

初态：对于j=0，即无背包空间分配，收益只能为0。对于i=0，没有i-1，状态方程为dp[0][j]=0/v[0](w[0]<=j)

int solution(int N, int W, vector<int> v, vector<int> w) {
	vector<vector<int>> dp(N, vector<int>(W+1));
	for (int i = dp.size()-1; i >= 0; i--)
		dp[i][0] = 0;
	for (int j = 1; j <= W;j++) {
		if (j > w[0]) dp[0][j] = v[0];
		else dp[0][j] = 0;
	}
	for(int i=1;i<N;i++)
		for (int j = 1; j <= W; j++) {
			if (w[i] > j) dp[i][j] = dp[i - 1][j];
			else {
				int y = dp[i - 1][j - w[i]] + v[i];
				int n = dp[i - 1][j];
				dp[i][j] = y > n ? y : n;
			}
		}
	return dp[N - 1][W];
	
}

附：

A.生成dp[i][j]时，选择购买i物品不一定比选择不购买i物品的收益