dp_dp渭tsmile-程序员宅基地

dp
在我看来就是把一个复杂的问题简单化,把简单的问题解决之后,从已知到未知的过程。其中关键的问题就是确定状态转移方程。找到问题的实质之后代码基本都一样。
下面是代码。思路可以参考下面我觉得很好理解的两个博客。
https://www.cnblogs.com/kkbill/p/12081172.html.
这上面的这个对于状态压缩讲的也很清楚。
https://www.cnblogs.com/mfrank/p/10533701.html.

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[1005];
struct fitting
{
	int val;
	int weight;
}a[22];
int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		int n, V;
		cin >> n >> V;
		for(int i=0; i<n; i++)
		cin >> a[i].val ;
		for(int i=0; i<n; i++)
		cin >> a[i].weight ;
		for(int i=0; i<n; i++)//第i个东西选或者不选 
		{
			for(int j=V; j>=a[i].weight; j--)
			dp[j] = max(dp[j], dp[j-a[i].weight] + a[i].val);//状态压缩
//				for(int nn=1;nn<=k;nn++)
//				{
//					for(int mm=1;mm<=V;mm++)
//					cout<<dp[mm][nn]<<" ";
//					cout<<endl;
//				}
//				cout<<endl;
		}
		cout << dp[V] << endl;
		memset(dp, 0, sizeof(dp));
	}
	
	return 0;
}

完全背包
关于多重背包,完全背包下面的这个博客讲的很清楚
动态规划:完全背包、多重背包.
在这种题目里每个物品都可以选择无限次。

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define inf 0x3f3f3f3f
int dp[10010];
int v[505],w[505];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(dp,inf,sizeof(dp));
		memset(v,0,sizeof(v));
		memset(w,0,sizeof(w));//记得该初始化别忘了
		dp[0]=0;
		int N,wei;
		scanf("%d%d",&N,&wei);//N:选择的物品个数,wei:背包重量
		for(int i=1;i<=N;i++)
		scanf("%d%d",&v[i],&w[i]);	
		for(int i=1;i<=N;i++)
		{
			for(int j=w[i];j<=wei;j++)/*理解了01为什么需要倒着就很容易
			理解这个为什么是从w[i]开始,这样会覆盖之前的选择。*/
			dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
//			for(int ii=1;ii<=wei;ii++)
//			cout<<dp[ii]<<" ";
//			cout<<endl;
		}
	}
	return 0;
}

多重背包
主要是运用了二进制的思想,把一个可能选择的分成多个。
代码

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 1000000
using namespace std;
 
int dp[MAX];//存储最后背包最大能存多少
int value[MAX],weight[MAX],number[MAX];//分别存的是物品的价值,每一个的重量以及数量
int bag;
 
void ZeroOnePack(int weight,int value )//01背包
{
    int i;
    for(i = bag; i>=weight; i--)
    {
        dp[i] = max(dp[i],dp[i-weight]+value);
    }
}
void CompletePack(int weight,int value)//完全背包
{
    int i;
    for(i = weight; i<=bag; i++)
    {
        dp[i] = max(dp[i],dp[i-weight]+value);
    }
}
 
void MultiplePack(int weight,int value,int number)//多重背包
{
    if(bag<=number*weight)//如果总容量比这个物品的容量要小,那么这个物品可以直到取完,相当于完全背包
    {
        CompletePack(weight,value);
        return ;
    }
    else//否则就将多重背包转化为01背包
    {
        int k = 1;
        while(k<=number)
        {
            ZeroOnePack(k*weight,k*value);
            number = number-k;
            k = 2*k;//这里采用二进制思想
        }
        ZeroOnePack(number*weight,number*value);
    }
}
int main()
{
    int n;
    while(~scanf("%d%d",&bag,&n))
    {
        int i,sum=0;
        for(i = 0; i<n; i++)
        {
            scanf("%d",&number[i]);//输入数量
            scanf("%d",&value[i]);//输入价值  此题没有物品的重量,可以理解为体积和价值相等
        }
        memset(dp,0,sizeof(dp));
        for(i = 0; i<n; i++)
        {
            MultiplePack(value[i],value[i],number[i]);//调用多重背包,注意穿参的时候分别是重量,价值和数量
        }
        cout<<dp[bag]<<endl;
    }
    return 0;
}

题解
https://vjudge.net/contest/423093#problem/K.
题目是给出硬币面额及每种硬币的个数,求从1到m能凑出面额的个数。
思路一开始就是以为用多重背包做,每个都分解一下,但是RE了,这就让我继续思考是否有其他更简洁的做法。最后看到题目只是在问能凑成的个数,直接分别取1-max不就行了吗,于是就有了下面的做法。

AC代码

#include <iostream>
#include <cstring>

using namespace std; 

int v[110], num[110], dp[100010], vis[100010];
 
int main()
{
    int n, m, k, ans;
    while(scanf("%d %d", &n, &m) && (n + m)) 
	{
        for(int i = 0; i < n; i++)
            scanf("%d", &v[i]);
        for(int i = 0; i < n; i++)
            scanf("%d", &num[i]);
        memset(vis, 0, sizeof(vis));
        ans = 0,vis[0] = 1;
        for(int i = 0; i < n; i++) 
		{
            memset(dp, 0, sizeof(dp));
            for(int j = v[i]; j <= m; j++) 
			{
                if(!vis[j] && vis[j - v[i]] 
				&& dp[j - v[i]] + 1 <= num[i]) 
				{
                    vis[j] = 1;
                    dp[j] = dp[j - v[i]] + 1; 
                    ans++;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

划分
题目:现有面值为1、2、3、4、5、6的硬币若干枚,现在需要知道能不能将这些硬币分成等额的两堆。
思路:很容易想到如果sum为奇数,一定不能分。如果sum是偶数,那就是多重背包看能否取到平均数。

#include<iostream>
#include<cstring>
using namespace std;

int dp[21*20000+20],heap[100];
int cn=0,cnt=1,sum;
void divide(int num,int value)
{
	int k=1;
	while(num>=k)
	{
		heap[cn++]=k*value;	
		num-=k;
		k*=2;
	}
	if(num)
	heap[cn++]=num*value;
}
void dpp()
{
	dp[0]=1;
	for(int i=0;i<cn;i++)
	{
		for(int j=sum/2;j>=heap[i];j--)
		if(dp[j-heap[i]])
		dp[j]=1;
	}
	if(dp[sum/2])
	{
		printf("Collection #%d:\n", cnt++);
    	printf("Can be divided.\n\n");
        return ;	
	}
	else
	{
		printf("Collection #%d:\n", cnt++);
        printf("Can't be divided.\n\n");
        return ;
	}
}
int main()
{
	int a,b,c,d,e,f;
	while(~scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f))
	{
		if(!a&&!b&&!c&&!d&&!e&&!f)
		return 0;

		sum=a+2*b+3*c+4*d+5*e+6*f;
		
		if(sum%2)
		{
			printf("Collection #%d:\n", cnt++);
            printf("Can't be divided.\n\n");
            continue;
		}
		memset(heap,0,sizeof(heap));
		memset(dp,0,sizeof(dp));
		cn=0;
		divide(a,1);divide(b,2);divide(c,3);
		divide(d,4);divide(e,5);divide(f,6);
		dpp();
	}
	return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_51681487/article/details/114240315

智能推荐

oracle split去逗号,行列转换_oracle拆分函数按逗号拆分 clob-程序员宅基地

文章浏览阅读3.6w次,点赞3次,收藏12次。1.针对 '1','2','3','4','5'(逗号在字符串外面)SQL> SELECT COLUMN_VALUE FROM TABLE(SYS.ODCIVARCHAR2LIST('1','2','3','4','5'));COLUMN_VALUE-----------------------------------------------------------------_oracle拆分函数按逗号拆分 clob

关于取整符号(二叉树具有n个结点的m次树的最小高度⌈logₘ(n(m-1)+1)⌉)_m叉树最小高度为啥向上取整-程序员宅基地

文章浏览阅读2.1k次。性质4 具有n个结点的m次树的最小高度为关于取整符号:向上取整⌈⌉和向下取整⌊⌋符号向下取整的运算称为Floor,用数学符号 ⌊ ⌋ 表示;向上取整的运算称为Ceiling,用数学符号 ⌈ ⌉ 表示。例如:⌊59/60⌋=0⌈59/60⌉=1⌊-59/60⌋=-1⌈-59/60⌉=0向上向下 取整函数数只会对小数点后面的 数字不为零 的数进行操作,要是给它一个整数 它就返回整数本..._m叉树最小高度为啥向上取整

Camera HAL3的整体架构和流程_mtk camera hal3-程序员宅基地

文章浏览阅读2.4k次,点赞10次,收藏42次。Camera的整体架构上图是Google官方的Camera架构,Google封装了HAL层接口:ICameraProvider, ICameraDevice, ICameraDeviceSession。这几个接口的作用如下:ICameraProvider:用于枚举单个设备并管理其状态。ICameraDevice:相机设备接口。ICameraDeviceSession:活跃的相机设备会话接口。MTK HAL3结构主要实现了这几个接口, CameraProviderImpl实现了IC._mtk camera hal3

解决maya导出alembic文件隐藏物体也导出的问题。_alembic maya-程序员宅基地

文章浏览阅读2.4k次。在cg制作过程中,我们经常会使用maya导出alembic文件,但是我发现有些情况下我们不需要把场景中的隐藏物体也导出_alembic maya

android textView设置html,解决图片和文字不对齐的问题_textview html.fromhtml 图品不居中问题-程序员宅基地

文章浏览阅读9.3k次,点赞2次,收藏7次。evernote中的笔记,这里分享一下:evernote笔记入口用textview可以显示html富文本,比显示单纯的文字要友好很多,效果图: 但是问题也很多。首先是 html 的支持实在有限,很多在html中比较easy的事情,在这里就感觉很困难,项目中遇到的两个问题: 1. 调整字体大小的时候,_textview html.fromhtml 图品不居中问题

MATLAB动态图画法-使用For命令实现重力加速度分叉_重力加速度matlab-程序员宅基地

文章浏览阅读837次。vx = 40;T = 0.01;t = 0:T:5;x = vx*t;y1 = -9.8*t.^2/2;y2 = 9.8*t.^2/2;figure()for i=1:(length(x)-1)axis([0,200,-100,100])X = x(i:i+1);Y1 = y1(i:i+1);Y2 = y2(i:i+1);plot(X,Y1);hold onplot..._重力加速度matlab

随便推点

阿里云OSS云存储删除(单个,指定的多个文件)删除文件_oss 删除指定文件夹内某一后缀的文件-程序员宅基地

文章浏览阅读6.1k次。阿里云OSS云存储删除(单个,指定的多个文件)删除文件_oss 删除指定文件夹内某一后缀的文件

Android 报错提示解决方法积累(不断更新)_declaration of 'okhttp3.internal.platform.platform-程序员宅基地

文章浏览阅读1.7k次。报错提示1java.lang.NoSuchMethodError: No virtual method log(ILjava/lang/String;Ljava/lang/Throwable;)V in class Lokhttp3/internal/platform/Platform; or its super classes (declaration of 'okhttp3.internal.platform.Platform' appears in /data/app/com.transforme_declaration of 'okhttp3.internal.platform.platform

android 11.0 去掉usb授权提示框 默认给予权限_android11 授予app所需的所有权限,例如:usb访问读写权限(不弹出授权框,默认允许),-程序员宅基地

文章浏览阅读4.2k次,点赞2次,收藏5次。在11.0 的产品开发中,在进行iot开发过程中,在插入usb设备时会弹出usb授权提示框,也带来一些不便,这个需要默认授予USB权限,插拔usb都不弹出usb弹窗所以这要从usb授权相关管理页默认给与usb权限。_android11 授予app所需的所有权限,例如:usb访问读写权限(不弹出授权框,默认允许),

Spring Boot 整合 JMS(ActiveMQ)_springboot jms-程序员宅基地

文章浏览阅读1.1k次。Spring Boot 整合 JMS(ActiveMQ)_springboot jms

HTML+CSS+JavaScript制作七夕表白网页(含音乐+自定义文字)_程序员网页表白制作-程序员宅基地

文章浏览阅读1.2w次,点赞23次,收藏131次。❉ HTML+CSS+JavaScript制作七夕表白网页(含音乐+自定义文字)一年一度的520情人节/七夕情人节/女朋友生日/程序员表白,是不是要给女朋友或者正在追求的妹子一点小惊喜呢,今天这篇博客就分享下前端代码如何实现HTML+CSS+JavaScript制作七夕表白网页(含音乐+自定义文字)。赶紧学会了,来制作属于我们程序员的浪漫吧!❉ 文章目录 ❉ HTML+CSS+JavaScript制作七夕表白网页(含音乐+自定义文字)❉ 效果演示❉ 代码文件目录一、文字修改(代码实现) _程序员网页表白制作

微信小程序常用组件视频课程-表单组件-checkbox-group 多项选择器 的使用_微信小程序 checkbox-group data-index-程序员宅基地

文章浏览阅读944次。js代码 /** * 页面的初始数据 */ data: { }, mycheck:function(e){ console.log(e.detail.value) },wxml代码<checkbox-group bindchange="mycheck"> <checkbox value='香蕉'>香蕉</check..._微信小程序 checkbox-group data-index

推荐文章

热门文章

相关标签