陈冠希

用户名：H2130819033

访问量：2877

签　名：

今日最爱，晚风与你

等　　级
排　　名	260
经　　验	5893
参赛次数	13
文章发表	31
年　　龄	20
在职情况	学生
学　　校	贺州学院
专　　业	软件工程

　　自我简介：

TA的其他文章

c++----map的统计功能
浏览：103

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

蓝桥杯算法提高VIP-01背包每一步都有注释，两种结构（易懂）

　　作者: 陈冠希　　　　发表时间：2022-07-23 22:52:04 浏览：53　|　评论：0　

原题链接：蓝桥杯算法提高VIP-01背包

#include<bits/stdc++.h>
using namespace std;
const int L = 5001;
int n,m;
int w[L],v[L];   //w为重量，v为价值   	
int dp[L][L]={0}; //记录第n件物品的重量，最优解
int main()
{
	cin>>n>>m;           //n为物品个数，m为背包能装重量 
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i]; //循环输入w和v 
	}
	for(int i=1;i<=n;i++)   //n个物品循环 
	{
		for(int j=0;j<=m;j++)   //m重量循环 
		{
			if(w[i]>j)           //如果第i个物品重量大于重量则dp[i][j]=上一个物品重量 
			dp[i][j]=dp[i-1][j];
			else
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
			//dp[i-1][j]为不偷
			//dp[i-1][j-w[i]]为偷取前一项物品，v[i]当前物品重量
			//求偷与不偷时的最大值即为最优解   
		}	
	}   
	cout<<dp[n][m];  //最后的数组即为最优解 
    return 0;
}
``````cpp

//方法二：结构体
#include<bits/stdc++.h>
using namespace std;
const int L = 5001;
int n,m;
int w[L],v[L];   //w为重量，v为价值   	
int dp[L][L]={0}; //记录第n件物品的重量，最优解
//背包问题通解 
int solve(int n,int m)
{
    for(int i=1;i<=n;i++)
        for (int j = 1; j <= m; j++)
        {
            if (w[i] > j)//装不了
                dp[i][j] = dp[i - 1][j];
            else//可以装下
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
        }
    return dp[n][m];
}

int main()
{
	cin>>n>>m;           //n为物品个数，m为背包能装重量 
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i]; //循环输入w和v 
	}
	cout<<solve(n,m); 
    return 0;
}

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

陈冠希

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-求PI* （C语言代码）

弟弟的作业（C++代码）

蓝桥杯算法提高VIP-01背包每一步都有注释，两种结构（易懂）

评论区

精彩推荐

简单的a+b （C语言代码）

数列排序（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

WU-拆分位数（C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

星期判断机（C语言代码）

数字游戏（C++代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

陈冠希

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-求PI* （C语言代码）

弟弟的作业 （C++代码）

蓝桥杯算法提高VIP-01背包 每一步都有注释，两种结构（易懂）

评论区

精彩推荐

简单的a+b （C语言代码）

数列排序 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

WU-拆分位数 （C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

星期判断机 （C语言代码）

数字游戏 （C++代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

弟弟的作业（C++代码）

蓝桥杯算法提高VIP-01背包每一步都有注释，两种结构（易懂）

　　评论区

数列排序（C语言代码）

WU-拆分位数（C++代码）

星期判断机（C语言代码）

数字游戏（C++代码）