01背包问题算是动态规划里经典中的经典了，没学过的同学之前应该也有所耳闻。江湖老规矩，先来描述一下什么是01背包问题。假设你有一个背包，最多能承重C千克，这里有k个物品，其重量分别为w1、w2、……、wk，其价值分别为v1、v2、……、vk，在背包所能承受的重量下，尽可能得使背包里的价值最大。（注意，该物品只能放或者不放，不能只放该物品的0.8这样子，非0即1，故称为01背包问题）此问题理解起来不难，那下面直接看题。
0-1背包问题 (转自PTA)
给定一个承重量为C的背包，n个重量分别为w1,w2,...,wn的物品，物品i放入背包能产生pi(>0)的价值(i=1,2,...,n)。
每个物品要么整个放入背包，要么不放。要求找出最大价值的装包方案。
输入的第一行包含两个正整数n和C(1≤n≤20)，第二行含n个正整数分别表示n个物品的重量，第三行含n个正整数分别表示n个物品放入背包能产生的价值。
在一行内输出结果，包括最大价值装包方案的价值、具体装包方案，用空格隔开。具体装包方案是n个物品的一个子集，用长度为n的0、1串表示（1表示对应物品被选中,0表示没有被选中）。如果这样的0、1串不唯一，取字典序最大的那个串。
4 9
2 3 4 5
3 4 5 7
12 1110
(注：1110 和0011都是价值最大的装包方案，取字典序最大的结果即为1110）
输出格式中有两个问题，第一是求出背包的最大价值，第二是价值最大的装包方案
问题一：求出背包的最大价值
for(int i=1;i<=n;i++)//物品i
{
for(int j=1;j<=c;j++)//重量j
{
if(j>=w[i])
{
arr[i][j]=max(arr[i-1][j],arr[i-1][j-w[i]]+v[i]);
}
else arr[i][j]=arr[i-1][j];
}
}我们先来理一下思路。面对这么多的物品，我们可以选择一个个地来装入背包，背包的承重量也一点点的提升，直至C(设立二维数组，列为物品i，行为背包的承重量)。假设当物品 i 的重量大于背包当前的总承重时，毋庸置疑，该物品不能放入背包；当物品 i 的重量小于背包的总承重时，我们就要进行对比，前面 i - 1个物品所带来的价值和现在要取出背包中的一部分物品用来存放物品i带来的价值，哪个更大？（取出多少呢，当然是刚好能放下物品 i 的重量，即w[ i ]），把更大的那个价值对当前背包价值进行更新。那么现在我们就能得出一个背包最大价值更新的公式：
arr[ i ][ j ] = max(arr[ i - 1 ][ j ], arr[ i - 1][ j - w[ i ] ] + v[ i ])，还不理解的同学看下图，参考题目的样例（看下面讲解的时候注意样例中对应的重量和价值）：
此二维数组是从上到下，从左到右看，arr[ i ][ j ]代表的是前 i 个物品在背包承重为 j 的时候的最大价值。先来看看物品1那一行是怎么得出来的？只有物品1的时候，无论背包承重多少，价值最大只能为3；再看看arr[ 3 ][ 7 ]，当背包重量为7时，因为arr[ 2 ][ 7 ]<arr[ 3 ][ 7 - 4 ] + 5，所以选择放入物品3。（如果选择不放入物品3时，前2个物品在背包重量为7的时候，价值为7，而当选择放入物品3时，价值为9，所以把arr[ 3 ][ 7 ]更新为9），其他的原理一样。求解得到的背包的最大价值是arr[ n ][ C ]，即前n个物品在背包最大承重为C的时候的最大价值。
问题二：打印价值最大的装包方案
int h=n,g=c;
while(h>=1)
{
if(arr[h][g]==arr[h-1][g])flag[h]=0;
else
{
flag[h]=1;
g=g-w[h];
}
h--;
}
for(int i=1;i<=n;i++)
{
printf("%d",flag[i]);
}理解该背包问题所求得的二维数组后，打印就不成问题了。
利用回溯法，从arr[ n ][ C ]开始回溯，当arr[ n ][ C ] == arr[ n - 1 ][ C ]时，说明有没有物品n都一样，即物品n没有放入背包中；当arr[ n ][ C ] != arr[ n - 1 ][ C ]时，说明物品n已经放入背包中，造成了背包价值的变化，物品 - - ，背包的重量也变成了C - w[ n ]，逐一回溯。
小细节：题目中要求输出字典序最大的结果，我们在求解最大价值的时候，也是按照前面的物品先放入背包，当且仅当后面物品放入的时候产生影响也考虑放入，所以我们回溯的时候得出的结果就是本题需要的答案。
ac代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
int w[21]={0};
int v[21]={0};
int flag[21]={0};
int arr[21][1024]={0};
int main()
{
int n=0,c=0;
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
}
for(int i=1;i<=n;i++)//物品i
{
for(int j=1;j<=c;j++)//重量j
{
if(j>=w[i])
{
arr[i][j]=max(arr[i-1][j],arr[i-1][j-w[i]]+v[i]);
}
else arr[i][j]=arr[i-1][j];
}
}
printf("%d ",arr[n][c]);
int h=n,g=c;
while(h>=1)
{
if(arr[h][g]==arr[h-1][g])flag[h]=0;
else
{
flag[h]=1;
g=g-w[h];
}
h--;
}
for(int i=1;i<=n;i++)
{
printf("%d",flag[i]);
}
return 0;
}希望能帮助到大家！
我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库，所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po
尝试通过RVM将RubyGems升级到版本1.8.10并出现此错误:$rvmrubygemslatestRemovingoldRubygemsfiles...Installingrubygems-1.8.10forruby-1.9.2-p180...ERROR:Errorrunning'GEM_PATH="/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/ruby-1.9.2-p180@global:/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/rub
我的最终目标是安装当前版本的RubyonRails。我在OSXMountainLion上运行。到目前为止，这是我的过程:已安装的RVM$\curl-Lhttps://get.rvm.io|bash-sstable检查已知(我假设已批准)安装$rvmlistknown我看到当前的稳定版本可用[ruby-]2.0.0[-p247]输入命令安装$rvminstall2.0.0-p247注意:我也试过这些安装命令$rvminstallruby-2.0.0-p247$rvminstallruby=2.0.0-p247我很快就无处可去了。结果:$rvminstall2.0.0-p247Search
由于fast-stemmer的问题，我很难安装我想要的任何rubygem。我把我得到的错误放在下面。Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingfast-stemmer:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcreatingMakefilemake"DESTDIR="cleanmake"DESTDIR=
当我尝试安装Ruby时遇到此错误。我试过查看this和this但无济于事➜~brewinstallrubyWarning:YouareusingOSX10.12.Wedonotprovidesupportforthispre-releaseversion.Youmayencounterbuildfailuresorotherbreakages.Pleasecreatepull-requestsinsteadoffilingissues.==>Installingdependenciesforruby:readline,libyaml,makedepend==>Installingrub
我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www
我意识到这可能是一个非常基本的问题，但我现在已经花了几天时间回过头来解决这个问题，但出于某种原因，Google就是没有帮助我。(我认为部分问题在于我是一个初学者，我不知道该问什么......)我也看过O'Reilly的RubyCookbook和RailsAPI，但我仍然停留在这个问题上.我找到了一些关于多态关系的信息，但它似乎不是我需要的(尽管如果我错了请告诉我)。我正在尝试调整MichaelHartl'stutorial创建一个包含用户、文章和评论的博客应用程序(不使用脚手架)。我希望评论既属于用户又属于文章。我的主要问题是:我不知道如何将当前文章的ID放入评论Controller。
首先回顾一下拉格朗日定理的内容：函数f(x)是在闭区间[a,b]上连续、开区间(a,b)上可导的函数，那么至少存在一个，使得:通过这个表达式我们可以知道，f(x)是函数的主体，a和b可以看作是主体函数f(x)中所取的两个值。那么可以有， 也就意味着我们可以用来替换 这种替换可以用在求某些多项式差的极限中。方法： 外层函数f(x)是一致的，并且h(x)和g(x)是等价无穷小。此时，利用拉格朗日定理，将原式替换为 ，再进行求解，往往会省去复合函数求极限的很多麻烦。使用要注意：1.要先找到主体函数f(x)，即外层函数必须相同。2.f(x)找到后，复合部分是等价无穷小。3.要满足作差的形式。如果是加
SPI接收数据左移一位问题目录SPI接收数据左移一位问题一、问题描述二、问题分析三、探究原理四、经验总结最近在工作在学习调试SPI的过程中遇到一个问题——接收数据整体向左移了一位（1bit）。SPI数据收发是数据交换，因此接收数据时从第二个字节开始才是有效数据，也就是数据整体向右移一个字节（1byte）。请教前辈之后也没有得到解决，通过在网上查阅前人经验终于解决问题，所以写一个避坑经验总结。实际背景：MCU与一款芯片使用spi通信，MCU作为主机，芯片作为从机。这款芯片采用的是它规定的六线SPI，多了两根线：RDY和INT，这样从机就可以主动请求主机给主机发送数据了。一、问题描述根据从机芯片手
文章目录git常用命令（简介，详细参数往下看）Git提交代码步骤gitpullgitstatusgitaddgitcommitgitpushgit代码冲突合并问题方法一：放弃本地代码方法二：合并代码常用命令以及详细参数gitadd将文件添加到仓库：gitdiff比较文件异同gitlog查看历史记录gitreset代码回滚版本库相关操作远程仓库相关操作分支相关操作创建分支查看分支：gitbranch合并分支：gitmerge删除分支：gitbranch-ddev查看分支合并图：gitlog–graph–pretty=oneline–abbrev-commit撤消某次提交git用户名密码相关配置g