01背包——four

userId_undefined

信奥教研部-陈婕

秩序白银

2023-08-20 19:23:53

发布于：浙江

8阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int dp[100][500];
int w[500],c[500];
int main(){
	int m,n;
	cin>>m>>n;//m背包容量   n物品数量
	for(int i=1;i<=n;i++){
		cin>>w[i]>>c[i];//w物品重量  c物品价值
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(j-w[i]>=0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);//放得下---不放，放 二者取大
			else dp[i][j]=dp[i-1][j];//放不下
		}
	}
	cout<<dp[n][m];//物品数量为n 背包容量为m时 背包内的最大价值
	return 0;
}
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论