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;
}
文章浏览阅读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
文章浏览阅读2.1k次。性质4 具有n个结点的m次树的最小高度为关于取整符号:向上取整⌈⌉和向下取整⌊⌋符号向下取整的运算称为Floor,用数学符号 ⌊ ⌋ 表示;向上取整的运算称为Ceiling,用数学符号 ⌈ ⌉ 表示。例如:⌊59/60⌋=0⌈59/60⌉=1⌊-59/60⌋=-1⌈-59/60⌉=0向上向下 取整函数数只会对小数点后面的 数字不为零 的数进行操作,要是给它一个整数 它就返回整数本..._m叉树最小高度为啥向上取整
文章浏览阅读2.4k次,点赞10次,收藏42次。Camera的整体架构上图是Google官方的Camera架构,Google封装了HAL层接口:ICameraProvider, ICameraDevice, ICameraDeviceSession。这几个接口的作用如下:ICameraProvider:用于枚举单个设备并管理其状态。ICameraDevice:相机设备接口。ICameraDeviceSession:活跃的相机设备会话接口。MTK HAL3结构主要实现了这几个接口, CameraProviderImpl实现了IC._mtk camera hal3
文章浏览阅读2.4k次。在cg制作过程中,我们经常会使用maya导出alembic文件,但是我发现有些情况下我们不需要把场景中的隐藏物体也导出_alembic maya
文章浏览阅读9.3k次,点赞2次,收藏7次。evernote中的笔记,这里分享一下:evernote笔记入口用textview可以显示html富文本,比显示单纯的文字要友好很多,效果图: 但是问题也很多。首先是 html 的支持实在有限,很多在html中比较easy的事情,在这里就感觉很困难,项目中遇到的两个问题: 1. 调整字体大小的时候,_textview html.fromhtml 图品不居中问题
文章浏览阅读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
文章浏览阅读6.1k次。阿里云OSS云存储删除(单个,指定的多个文件)删除文件_oss 删除指定文件夹内某一后缀的文件
文章浏览阅读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
文章浏览阅读4.2k次,点赞2次,收藏5次。在11.0 的产品开发中,在进行iot开发过程中,在插入usb设备时会弹出usb授权提示框,也带来一些不便,这个需要默认授予USB权限,插拔usb都不弹出usb弹窗所以这要从usb授权相关管理页默认给与usb权限。_android11 授予app所需的所有权限,例如:usb访问读写权限(不弹出授权框,默认允许),
文章浏览阅读1.1k次。Spring Boot 整合 JMS(ActiveMQ)_springboot jms
文章浏览阅读1.2w次,点赞23次,收藏131次。❉ HTML+CSS+JavaScript制作七夕表白网页(含音乐+自定义文字)一年一度的520情人节/七夕情人节/女朋友生日/程序员表白,是不是要给女朋友或者正在追求的妹子一点小惊喜呢,今天这篇博客就分享下前端代码如何实现HTML+CSS+JavaScript制作七夕表白网页(含音乐+自定义文字)。赶紧学会了,来制作属于我们程序员的浪漫吧!❉ 文章目录 ❉ HTML+CSS+JavaScript制作七夕表白网页(含音乐+自定义文字)❉ 效果演示❉ 代码文件目录一、文字修改(代码实现) _程序员网页表白制作
文章浏览阅读944次。js代码 /** * 页面的初始数据 */ data: { }, mycheck:function(e){ console.log(e.detail.value) },wxml代码<checkbox-group bindchange="mycheck"> <checkbox value='香蕉'>香蕉</check..._微信小程序 checkbox-group data-index