标签：背包 容量 int 问题 DP dp SIZE

背包问题

0-1背包

动态转移方程

\(dp_{i,j}\)代表在背包容量只有\(i\)的时候，拿前\(j\)件物体能拿最大的价值。

\[ \begin{cases} dp_{i,j}=dp_{i,j-1}(背包容量不够时,W_i>j)\\ dp_{i,j}=\max(dp_{i,j-1},dp_{i-W_j,j-1}+V_i)(背包容量够时,W_i \le j) \end{cases}\]

初值

\(dp_{i,0}=0,dp_{0,j=0}\)，因为只有\(0\)件物体只能拿价值总和为\(0\)的物体而背包容量只有\(0\)也只能拿价值总和为\(0\)的物体。

终值

\(dp_{w,n}\)
因为\(dp_{i,j}\)代表在背包容量只有\(i\)的时候，拿前\(j\)件物体能拿最大的价值。
而要求在背包容量只有\(w\)的时候，拿前\(n\)件物体(全部物体)能拿最大的价值。

code

code1

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 205;
int main() {
	int W[SIZE], C[SIZE], M, N; //W容量，C价值，M背包容量，N物品数量
	int DP[SIZE][SIZE];         //i容量 j物品
	cin >> M >> N;
	for (int i = 1; i <= N; i++) cin >> W[i] >> C[i];
	for (int i = 0; i <= M; i++)DP[i][0] = 0;
	for (int i = 0; i <= N; i++)DP[0][i] = 0;
	for (int i = 1; i <= N; i++)//枚举物品
		for (int j = 0; j <= M; j++) //枚举容量
			if (W[i] > j) DP[j][i] = DP[j][i - 1];
			else          DP[j][i] = max(DP[j - W[i]][i - 1] + C[i], DP[j][i - 1]);
	cout << DP[M][N];
	return 0;
}

code2

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 205;
int main() {
	int W[SIZE], C[SIZE], M, N; 			//W容量，C价值，M背包容量，N物品数量
	int DP[SIZE] = {};       				//i容量 j物品
	cin >> M >> N;
	for (int i = 1; i <= N; i++) cin >> W[i] >> C[i];
	for (int i = 1; i <= N; i++)			//枚举物品
		for (int j = M; j >= 0; j--)	    //枚举容量 
			if (W[i] > j) DP[j] = DP[j];
			else          DP[j] = max(DP[j - W[i]] + C[i], DP[j]);
	cout << DP[M];
	return 0;
}
//10：14 注意：要逆向 

标签：背包,容量,int,问题,DP,dp,SIZE
From： https://www.cnblogs.com/kimi-learn/p/17035025.html