解题思路:动态规划dp解法
for循环i不断加入砝码
当前状态=不加/右加/左加 :dp[i+1][j]=dp[i][j] || dp[i][j+w[i]] || dp[i][abs(j-w[i])];
参考代码:
#include<bits/stdc++.h> using namespace std; int main() { int n; int size=0; cin>>n; vector<int> w(n); for(int i=0;i<n;i++){ cin>>w[i]; size+=w[i]; } vector<vector<bool> > dp(n+1,vector<bool>(size+1,false)); //设定初始状态,(j==w[i]时,dp[?][j-w[i]=0]=true) dp[0][0]=true; for(int i=0;i<n;i++){ for(int j=size;j>=0;j--){ //dp[i][j+w[i]]中j+w[i]可能数组过界需要判断 //使用大数组,例如dp[102][100003] 就不用判断过界,但是大数组无法使用局部变量,记得使用全局变量 if(j<size+1-w[i]){ dp[i+1][j]=dp[i][j] || dp[i][j+w[i]] || dp[i][abs(j-w[i])]; }else{ dp[i+1][j]=dp[i][j] || dp[i][abs(j-w[i])]; } } } int res=0; for(int i=1;i<=size;i++){ if(dp[n][i]){ res++; } } cout<<res; return 0; }
0.0分
12 人评分
蛇行矩阵 (C语言代码)浏览:753 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:1197 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:1163 |
WU-整数平均值 (C++代码)浏览:1246 |
简单的a+b (C语言代码)浏览:529 |
2005年春浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:597 |
图形输出 (C语言代码)浏览:949 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:403 |
C语言程序设计教程(第三版)课后习题10.1 (C++代码)浏览:503 |
1073题解浏览:625 |