备案网站名称攻略,网页视频怎么下载到本地手机,云服务器搭建,淄博网络推广公司题目描述#xff1a; 题目分析#xff1a; 我也没有完全搞太明白#xff0c;简单说说我的理解
1.dp【i】【j】表示前 i 个砝码#xff0c;是否可以称出来重量为 j 的物品#xff0c;如果可以的话#xff0c;值为1#xff0c;不可以
为0#xff1b;
2.针对当前第 i 个…题目描述 题目分析 我也没有完全搞太明白简单说说我的理解
1.dp【i】【j】表示前 i 个砝码是否可以称出来重量为 j 的物品如果可以的话值为1不可以
为0
2.针对当前第 i 个砝码一共有三种选择分别是放到左边、右边又或者是不放该砝码【优先将砝码放在右边】
如题例所示第一个砝码【重 1】可以称重 0 与 1 两个重量
此时开始处理第二个砝码重 4
第一种将砝码放在右边那么右边砝码的重量就是 1 4 5可以称出质量为 5 的物品则dp【2】【5】 1
第二种将砝码放在左边那么右边砝码的重量就是 1 左边砝码质量为 4 可以称出质量为 3 的物品则dp【2】【3】 1
第三种不放砝码可以称出质量为 1 的物品则dp【2】【1】 1
但是如何用动态规划的思路将再这种思想用编程实现了
首先设定初始值当 0 个砝码时只有 重量 0 可以被称出来令dp【0】【0】 1其余值全部为0
接下来处理第一个砝码依次判断dp【1】【j】的值那怎么判断呢 根据状态转移式: dp[i][j] max(dp[i-1][j],max(dp[i-1][jw[i]],dp[i-1][abs(j-w[i])])); 首先是dp【1】【0】 max(dp[0][0],max(dp[0][1],dp[0][1])) 1;
解释dp[0][0]既然不放第 1 个物品质量 0 就被称出来了那么加上砝码 1 也可以称出来质量 0 dp[0][1]、dp[0][1]表示前0个砝码的组合是否可以称出质量为4的物品。那肯定不可以所以表达式dp【1】【0】的值就是1表示前1个砝码可以称出体积为 0 的物品
接下来判断dp【1】【1】前前1个砝码可以称出体积为 1 的物品
dp【1】【1】 max(dp[0][1],max(dp[0][2],dp[0][0]))
解释dp[0][1] 0、dp[0][2] 0【这个式子表示将第一个砝码放在右边的情况只要这个dp[0][2] 1说明可以称出来质量为2的物品那么就能dp[1][1]也一定能成功因为将该砝码放到左边为了保持平衡左边要再添加重量为 1 的物品这样也就被称出来了】意思好像是加在右边的话是通过左边加物品实现平衡的
dp[0][0] 1【表示将砝码放在左边的情况】
再举个例子dp【3】【7】
dp【2】【7】
dp【2】【7 6】如果为真那就说明前两个砝码可以称出质量为13的物品那么把该砝码放到天平左侧为了保持平衡左侧还需要添加质量为7的物品那么质量为7的物品就被测量出来了
dp【2】【7 - 6】如果为真那就说明前两个砝码可以称出质量为1的物品那么把该砝码放到天平右侧为了保持平衡左侧还需要添加质量为7的物品那么质量为7的物品就被测量出来了
题解代码 dsp: //砝码称重--一半的分
#include bits/stdc.h
using namespace std;
const int vinf 1e5100; //砝码之和最大
int vis[vinf]; //用来标记该质量是否可以被称重
int n;
int val[vinf];
void dfs(int x,int y)
{if(yn1){if(x0){vis[x]1;coutxendl;} return;}//开始深搜dfs(x val[y],y 1); // 砝码放到左边 dfs(x - val[y],y 1); //砝码放到右边 dfs(x,y1);
}
int main(){cinn;//输入砝码的重量for(int i1;in;i){//cinval[i]; //打印出可以撑出来的 }//已经读取了砝码的重量dfs(0,0); //初始状态左边为已经平衡的天平左边的重量右边为第 i 个砝码//开始枚举每一个重量int ans 0; for(int i1;ivinf;i){if(vis[i]) ans; }coutendlansendl;return 0;
} dp //砝码称重--dp
#include bits/stdc.h
using namespace std;
int n,w[110];
int dp[110][100005];
int ans 0;
int main(){cinn;int sum0;for(int i1;in;i){cinw[i];sumw[i];}dp[0][0]1;for(int i1;in;i){for(int j0;jsum;j){dp[i][j] max(dp[i-1][j],max(dp[i-1][jw[i]],dp[i-1][abs(j-w[i])]));}}for(int i1;isum;i){if(dp[n][i])ans;}coutansendl; return 0;
}
