完全背包问题

完全背包就是相对于01背包来说没有物品数量的限制，物品的数量是无限的，你可以那背包全装同一件物品

01背包问题

二位数组：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])

一维数组滚动优化：

在01背包里面有，这里就不多赘述

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

完全背包：每个物品有无限个

Dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i])

经过变换等同于

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

具体原因看下面资料，在经过一系列数学操作后，完全背包和01背包的状态转移方程还有后面的i和i-1的区别

参考资料：完全背包问题求解-NOIP/CSP/蓝桥杯算法试学课-青少年C++编程_哔哩哔哩_bilibili

#include<iostream>
#include<algorithm>
using namespace std;
//完全背包问题
int dp[100010], c, wi, vi, n;//c是背包容量，wi是重量，vi是药草价值，n是n个物品
int main() {
	cin >> c >> n;
	for (int i = 1; i <= n; i++) {
		cin >> wi >> vi;
		for (int j = wi; j <= c; j++) {
			dp[j] = max(dp[j], dp[j - wi] + vi);
		}
	}
	cout << dp[c] << endl;
	return 0;
}



//最暴力的写法
	//int n, m;//n是体积，m是可用物品
	//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 = 1; j <= m; j++) {
	//		for (int k = 0; k * v[i] < j; k++) {
			f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    //应该是这句
    //          f[i][j] = max( f[i - 1][j - k * v[i]] + k * w[i]);
	//		}
	//	}
	//}
	//cout << f[n][m] << endl;