[Acwing] 算法基础课汇总五 动态规划 一

背包问题 01背包问题

状态表示 : f [ i ] [ j ] f[i][j] f[i][j] 前 i i i个物品中,体积为 j j j的最大价值

状态转移 : f [ i ] [ j ] = f [ i − 1 ] [ j ] ( j − v < 0 ) f[i][j] =f[i-1][j](j-v>w[i]>>s[i]; for(int i=1;i=0;j--) { for(int k=1;km; for(int i = 1;i>v>>w>>s; for(int k = 1;k= k*v;j--) f[j] = max(f[j],f[j-k*v]+k*w); s-=k; } if(s) { for(int j = m ;j>=s*v;j--) { f[j] = max(f[j],f[j-s*v]+s*w); } } } coutm; for(int i=0;i>s[i]; for(int j=0;j>v[i][j]>>w[i][j]; } } for(int i=0;i=0;j--){ for(int k=0;k=1;k--)也可以 if(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); } } } cout