D4239 【例9.12】完全背包问题

#include<bits/stdc++.h>
using namespace std;
/*
1.确定状态
dp[i][j]表示前面i种物品中背包容量为j时能获得的最大价值
2.确定答案
dp[n][m]
3. 状态转移方程
不装或装不下 dp[i][j]=dp[i-1][j]
装得下 dp[i][j]=dp[i][j-w[i]]+c[i] 需要比较装得下或不装 装不下哪个更优 
4. 初始值
dp[0][j]=0; 
*/

int n,m;
int w[35],c[35];
int dp[35][205];
int main(){
	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=0;j<=m;j++){
			dp[i][j]=dp[i-1][j];
			if(j>=w[i]){
				dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+c[i]);
			}
		}
	}
	cout<<"max="<<dp[n][m];
	return 0;
}