D4239 【例9.12】完全背包问题

liu_zheng · 2025-02-06 16:16:53 · 个人记录

#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;
}