背包问题解法

背包直接秒了

#include<bits/stdc++.h>
using namespace std;
int m,n;                    // m: 背包容量, n: 物品数量
int p[10005],w[1005],dp[10005][3005];  // p: 物品价值, w: 物品重量, dp: 动态规划数组
int main(){
	cin>>m>>n;              // 输入背包容量和物品数量
	for(int i=1;i<=n;i++){
		cin>>w[i]>>p[i];    // 输入每个物品的重量和价值
	}
	for(int i=1;i<=n;i++){          // 遍历每个物品
		for(int j=1;j<=m;j++){      // 遍历背包容量
			if(w[i]<=j){            // 如果当前物品可以放入容量为j的背包
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);  // 状态转移: 不选或选当前物品
            }else{
                dp[i][j]=dp[i-1][j];  // 放不下, 继承上一行的状态
            }
		}
	}
	cout<<dp[n][m];           // 输出最大价值
	return 0;
}