小哈哈

用户名：20180390139

访问量：19724

签　名：

世界上怎么会有那么聪明的人呢？

等　　级
排　　名	216
经　　验	6366
参赛次数	9
文章发表	38
年　　龄	0
在职情况	学生
学　　校	蓝翔挖掘机技校
专　　业	网络工程

　　自我简介：

我是个傻嗨，但是我会努力像个正常人

TA的其他文章

连通图 -题解(C语言代码)---------------典型的BFS扩充节点（简单详细代码）
浏览：361

EXCEL排序-题解(C++代码)---------要注意一个地方，容易错
浏览：720

数据结构-最小生成树-题解(C语言代码)-----------并查集Kruskal算法
浏览：733

你可能喜欢

P1016-题解(C语言代码)------动态规划，通俗详细描述

　　作者: 小哈哈　　　　发表时间：2019-08-31 07:58:49 浏览：580　|　评论：1　

原题链接：[NOIP2001]装箱问题

其实这是一道典型的01背包问题，我们之前看的01背包问题问的是  一个背包和n件物品，每个物品都有它自己的价值，然后怎么拿才能让背包装的物品总价值最大。
	然而这道题其实只是改一下，把价值改成了体积，怎么拿才能让背包的体积最小，其实如果你知道怎么拿让背包装的东西的体积最大，那么你就可以知道它体积最小能剩下多少了
	接下来用动态规划求解
	#include<stdio.h>
    #define N 20001
    int main(){
    	int i,j;
    	int v,n,A[50]={0},dp[N]={0};//例如dp[20]的意思是：容量为20的背包最多能装多少体积的东西，dp[30]的意思是：容量为30的背包最多能装多少体积的东西，
    	scanf("%d",&v);
    	scanf("%d",&n);
    	for(i=1;i<=n;i++){
    		scanf("%d",&A[i]);
    	}
    
    	for(i=1;i<=n;i++){
    		for(j=v;j>=A[i];j--){  //为什么j是从最大减下来，而不是从1开始加呢，因为每个物品的数量是有限的，比如如果dp[30]在dp[20]的基础上加了A[i]=10，表示30容量这个背包它拿了A[i]=10这个东西了，但是-----它没有考虑：dp[20]里面是否拿过A[i]=10这个东西，所以要j--;
    			
    				dp[j]=dp[j]>dp[j-A[i]]+A[i] ?dp[j]:dp[j-A[i]]+A[i];//这是个状态转移方程，别看它难看你可以理解为:
					dp[j]=max(  dp[j-A[i]]+A[i]  ,  dp[j]  )也就是我要知道容量为30的背包最多能装多少东西，我只要看看容量为 30-A[i] 这个背包最多能装多少东西就行了，然后比较大小
					比如容量为30的背包最多能装多少东西呢？，你如果知道容量为20的背包最多能装18这么多东西，而且刚好还有个东西的大小为10，那么你肯定会在20背包的基础上拿起这个容量为10的东西呀，所以30背包能装28这么多东西，然后你又知道容量为25的背包最多能装25这么多东西，而且你又知道还有个东西的容量为5，所以你肯定会在25这个背包的基础上拿起大小为5这个东西啊，所以30这个背包“还”可以装25+5=30这么多东西，
					而30>28，所以dp[30]=30咯
					也就是dp[30]=max(dp[20]+10,dp[25]+5)，从而dp[30]=30;这只是个例子，方便理解
    			
    		}
    	}
    
    	printf("%d\n",v-dp[v]);//如果你都知道容量为v的背包最多能装多少东西了，你直接用v-dp[v]不就是背包最小能剩下多少体积吗
    	return 0;
    }

0.0分

8 人评分

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

　　评论区

七巷少年

牛批牛批，我很喜欢老哥写的注释

2022-07-14 22:42:25

小哈哈

TA的其他文章

你可能喜欢

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

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

C二级辅导-统计字符（C语言代码）

数字整除（C语言代码）

人民币问题（C语言代码）

P1016-题解(C语言代码)------动态规划，通俗详细描述

评论区

精彩推荐

C语言训练-委派任务* （C语言代码）..................竟然是第一个

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

数列排序（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

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

WU-图形输出（C++代码）

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

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

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

敲七（C语言代码）

小哈哈

TA的其他文章

你可能喜欢

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

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

C二级辅导-统计字符 （C语言代码）

数字整除 （C语言代码）

人民币问题 （C语言代码）

P1016-题解(C语言代码)------动态规划，通俗详细描述

评论区

精彩推荐

C语言训练-委派任务* （C语言代码）..................竟然是第一个

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

数列排序 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

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

WU-图形输出 （C++代码）

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

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

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

敲七 （C语言代码）

C二级辅导-统计字符（C语言代码）

数字整除（C语言代码）

人民币问题（C语言代码）

　　评论区

数列排序（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

WU-图形输出（C++代码）

敲七（C语言代码）