程序员界的菜鸟

用户名：Aqi

访问量：4308

签　名：

hello world!!

等　　级
排　　名	7597
经　　验	1299
参赛次数	1
文章发表	6
年　　龄	22
在职情况	学生
学　　校	郑州大学
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

C语言训练-用动态规划解决——斐波纳契数列（C语言代码）
浏览：1355

蓝桥杯算法提高VIP-01背包-完全背包题解（C语言代码）
浏览：724

你可能喜欢

A+B for Input-Output Practice (III) （C语言代码）

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

蓝桥杯算法提高VIP-01背包-完全背包题解（C语言代码）

　　作者: 程序员界的菜鸟　　　　发表时间：2020-05-16 02:29:27 浏览：724　|　评论：0　

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

# 废话不多说，直接上代码
**0-1背包问题**
原题链接：——>[0-1背包问题](https://www.dotcpp.com/oj/problem1924.html "0-1背包问题")

```c
#include <stdio.h>

int main()
{
	int n,max;//n表示物品个数，max表示背包容量 
	scanf("%d%d", &n, &max);
	int weight[n];//存储物品重量的数组
	int value[n];//存储物品价值的数组
	int i = 0;
	while(i< n){
		scanf("%d%d", &weight[i], &value[i]);
		i++;
	}
	
	int opt[n+1][max+1];//存储每一步选择后的最大价值，即opt[i][w]表示当可选物品为i个，背包容量为w时，所能背的最大价值
	
	for(int i = 0; i<=max; i++){//当n=0,即可选择的物品为0时，无论背包容量再大，此时的最大价值也为0，因为此时没有物品可装
		opt[0][i] = 0;
	}
	
	for(int i = 0; i<=n; i++){//当max=0,即背包容量为0时，即使有再多可选择的物品，此时的最大价值也为0，因为没有容量的背包装不下任何物品
		opt[i][0] = 0;
	}
	
	for(int i= 1; i<=n; i++){
		for(int w = 1; w<=max; w++){
			if(w-weight[i-1] < 0){//当背包容量没有当前物品大时，此时只有一种选择，就是不选
				opt[i][w] = opt[i-1][w];
			}else{//当背包容量足够容纳当前物品时，此时有两种选择：即装下这个物品和不装这个物品，我们应该取这两种选择所能创造的价值最大的那个
				int a = opt[i-1][w-weight[i-1]] + value[i-1];//装下该物品创造的价值
				int b = opt[i-1][w];//不装该物品创造的价值
				if(a>b){//当装下该物品创造的价值更大时，就选择装下
					opt[i][w] = a;
				}else{//当不装该物品创造的价值更大时，就选择不装
					opt[i][w] = b;
				}
			}
		}
	}
	printf("%d", opt[n][max]);
	return 0;
 } 
```
**完全背包问题**
原题链接：——>[完全背包问题](https://www.dotcpp.com/oj/problem2132.html "完全背包问题")
0-1背包问题与完全背包问题的区别就是：0-1背包不能重复选择，而完全背包可以重复选择
解题思路与0-1背包完全一样，只需将上述代码做一处小小的改动，即可应用于完全背包问题
即将第30行代码

int a = opt[i-1][w-weight[i-1]] + value[i-1];//装下该物品创造的价值
改成下面即可：

int a = opt[i][w-weight[i-1]] + value[i-1];//装下该物品创造的价值
有问题请留言！！

0.0分

4 人评分

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

程序员界的菜鸟

TA的其他文章

你可能喜欢

字符串输入输出函数（Java代码）

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

A+B for Input-Output Practice (III) （C语言代码）

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

母牛的故事（C语言代码）

蓝桥杯算法提高VIP-01背包-完全背包题解（C语言代码）

评论区

精彩推荐

C语言训练-阿姆斯特朗数（C语言代码）

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

破解简单密码（C语言代码）

模拟计算器（C语言代码）

简单编码（C++代码）

C语言训练-大、小写问题（C语言代码）

字符串输入输出函数（Java代码）

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

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

校门外的树（C语言代码）

程序员界的菜鸟

TA的其他文章

你可能喜欢

字符串输入输出函数 （Java代码）

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

A+B for Input-Output Practice (III) （C语言代码）

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

母牛的故事 （C语言代码）

蓝桥杯算法提高VIP-01背包-完全背包 题解（C语言代码）

评论区

精彩推荐

C语言训练-阿姆斯特朗数 （C语言代码）

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

破解简单密码 （C语言代码）

模拟计算器 （C语言代码）

简单编码 （C++代码）

C语言训练-大、小写问题 （C语言代码）

字符串输入输出函数 （Java代码）

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

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

校门外的树 （C语言代码）

字符串输入输出函数（Java代码）

母牛的故事（C语言代码）

蓝桥杯算法提高VIP-01背包-完全背包题解（C语言代码）

　　评论区

C语言训练-阿姆斯特朗数（C语言代码）

破解简单密码（C语言代码）

模拟计算器（C语言代码）

简单编码（C++代码）

C语言训练-大、小写问题（C语言代码）

字符串输入输出函数（Java代码）

校门外的树（C语言代码）