网站建立的公司,网站建设公司的排名,家具网站怎么做,绩溪住房建设网站欢迎来到Cefler的博客#x1f601; #x1f54c;博客主页#xff1a;折纸花满衣 #x1f3e0;个人专栏#xff1a;题目解析 #x1f30e;推荐文章#xff1a;【LeetCode】winter vacation training 目录 #x1f449;#x1f3fb;完全背包 #x1f449;#x1f3fb;… 欢迎来到Cefler的博客 博客主页折纸花满衣 个人专栏题目解析 推荐文章【LeetCode】winter vacation training 目录 完全背包 完全背包
原题链接完全背包 mycode1(超出时间限制):
#include iostream
#includevector
using namespace std;int main() {int n, V;cin n V;vectorint w(n 1), v(n 1);// vectorvectorint goods(n,vectorint(2));for (int k 1; k n; k) cin v[k] w[k];//创建dp表vectorvectorint dp1(n 1, vectorint(V 1)), dp2(n 1, vectorint(V 1));//dp表初始化for (int k 1; k V 1; k){dp2[0][k] -1;}//开始填表for (int i 1; i n 1; i){for (int j 1; j V 1; j){// dp1[i][j]特征方程dp1[i][j] dp1[i - 1][j];int num 1;if (j - v[i] 0){dp1[i][j] max(dp1[i][j], w[i] * num dp1[i - 1][j - v[i] * num]);//一定要在这个位置先放一个可能第一个就是最大(调试出来的血泪)for (; j - v[i] * num 0; num){dp1[i][j] max(dp1[i][j], w[i] * num dp1[i - 1][j - v[i] * num]);}//--num;//因为此时j - v[i] * num已经0所以此时要--num恢复j - v[i] * num 0的num状态//dp1[i][j] max(dp1[i][j], w[i] * num dp1[i - 1][j - v[i] * num]);}//dp2[i][j]特征方程num 1;//num重新初始化为1dp2[i][j] dp2[i - 1][j];if (j - v[i] 0 dp2[i ][j - v[i]] ! -1){dp2[i][j] max(dp2[i][j], w[i] * num dp2[i][j - v[i] * num]);//一定要在这个位置先放一个可能第一个就是最大(调试出来的血泪)for (; j - v[i] * num 0 dp2[i][j - v[i] * num] ! -1; num){dp2[i][j] max(dp2[i][j], w[i] * num dp2[i][j - v[i] * num]);}//--num;//因为此时j - v[i] * num已经0所以此时要--num恢复j - v[i] * num 0的num状态//dp2[i][j] max(dp2[i][j], w[i] * num dp2[i][j - v[i] * num]);}}}cout dp1[n][V] endl;cout (dp2[n][V] -1 ? 0 : dp2[n][V]) endl;
} 我好不容易心动一次你却让我输得这么彻底~呵呵 优化代码
这里主要优化了状态转移方程 mycode2:
#include iostream
#includevector
using namespace std;
int main() {int n, V;cin n V;vectorint w(n 1), v(n 1);// vectorvectorint goods(n,vectorint(2));for (int i 1; i n; i) cin v[i] w[i];//创建dp表vectorvectorint dp1(n 1, vectorint(V 1)), dp2(n 1, vectorint(V 1));//dp表初始化for (int i 1; i V 1; i){dp2[0][i] -1;}//开始填表for (int i 1; i n 1; i){for (int j 0; j V 1; j){//dp1[i][j]特征方程dp1[i][j] dp1[i - 1][j];if (j - v[i] 0)dp1[i][j] max(dp1[i][j], w[i] dp1[i ][j - v[i]]);//dp2[i][j]特征方程dp2[i][j] dp2[i - 1][j];if (j - v[i] 0 dp2[i][j - v[i]] ! -1)dp2[i][j] max(dp2[i][j], w[i] dp2[i][j - v[i]]);}}cout dp1[n][V] endl;cout (dp2[n][V] -1 ? 0 : dp2[n][V]) endl;
}
