10分求助
查看原帖
10分求助
655995
realyanhualengluo楼主2023/2/22 22:44

只对了第一个点

#include<iostream>
#include<algorithm>
using namespace std;
int w[1000];//时间 
int c[1000];//价值 
int dp[100][100];//第i个物品,恰好装满重量为v的背包 
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>w[i]>>c[i];
	}
	//初始化dp数组
	dp[0][0]=0;
	//状态转移方程
	for(int i=1;i<=m;i++){
		for(int v=w[i];v<=n;v++){
			dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
		}
	} 
	//cout<<dp[n][m];
	cout<<dp[m][n];
}
2023/2/22 22:44
加载中...