软件公司门户网站模板,重庆网站推广机构,用软件做模板下载网站,给企业建设网站的流程图题目描述 即0-1背包#xff0c;把每个物品只能拿一次改为能拿无数次。 思路 //这个位置的状态是不拿#xff0c;第一次拿#xff0c;和第n1次拿
dp[i][j]max(max(dp[i-1][j],dp[i-1][j-v[i]]w[i]),dp[i][j-v[i]]); 拿0次#xff1a;dp[i-1][j];
拿1次#xff1a;dp[i-…题目描述 即0-1背包把每个物品只能拿一次改为能拿无数次。 思路 //这个位置的状态是不拿第一次拿和第n1次拿
dp[i][j]max(max(dp[i-1][j],dp[i-1][j-v[i]]w[i]),dp[i][j-v[i]]); 拿0次dp[i-1][j];
拿1次dp[i-1][j-v[i]]w[i];
拿2次dp[i-1][j-v[i]*2]w[i]*2;
拿3次dp[i-1][j-v[i]*3]w[i]*3;
拿n次dp[i-1][j-v[i]*n]w[i]*n;
在拿了一次之后dp[i][j]更新为dp[i-1][j-v[i]]w[i];
拿第二次时可以直接拿第一次拿的结论d[i][j-v[i]]直接转移。 一维数组优化 #include bits/stdc.h
using namespace std;
int dp[1000];
int main(){int w[110],v[110];int t,m;cintm;for(int i1;im;i){cinw[i]v[i];}for(int i1;im;i){for(int j0;jt;j){//0-1背包是从后往前千万不要弄混if(jw[i]){dp[j]max(dp[j],dp[j-w[i]]v[i]);}else{dp[j]dp[j];}}}
/* for(int i0;im;i){for(int j0;jt;j){coutdp[i][j] ;}coutendl;}
*/ coutdp[t];return 0;
} 转载于:https://www.cnblogs.com/nodeee/articles/11032662.html
