完全背包

it2026-09-04 6

所有背包思想来自闫总的ACWing

题目链接：https://www.acwing.com/problem/content/3/

#mermaid-svg-TubERLLvcxBxGhFG .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-TubERLLvcxBxGhFG .label text{fill:#333}#mermaid-svg-TubERLLvcxBxGhFG .node rect,#mermaid-svg-TubERLLvcxBxGhFG .node circle,#mermaid-svg-TubERLLvcxBxGhFG .node ellipse,#mermaid-svg-TubERLLvcxBxGhFG .node polygon,#mermaid-svg-TubERLLvcxBxGhFG .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-TubERLLvcxBxGhFG .node .label{text-align:center;fill:#333}#mermaid-svg-TubERLLvcxBxGhFG .node.clickable{cursor:pointer}#mermaid-svg-TubERLLvcxBxGhFG .arrowheadPath{fill:#333}#mermaid-svg-TubERLLvcxBxGhFG .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-TubERLLvcxBxGhFG .flowchart-link{stroke:#333;fill:none}#mermaid-svg-TubERLLvcxBxGhFG .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-TubERLLvcxBxGhFG .edgeLabel rect{opacity:0.9}#mermaid-svg-TubERLLvcxBxGhFG .edgeLabel span{color:#333}#mermaid-svg-TubERLLvcxBxGhFG .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-TubERLLvcxBxGhFG .cluster text{fill:#333}#mermaid-svg-TubERLLvcxBxGhFG div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-TubERLLvcxBxGhFG .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-TubERLLvcxBxGhFG text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-TubERLLvcxBxGhFG .actor-line{stroke:grey}#mermaid-svg-TubERLLvcxBxGhFG .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-TubERLLvcxBxGhFG .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-TubERLLvcxBxGhFG #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-TubERLLvcxBxGhFG .sequenceNumber{fill:#fff}#mermaid-svg-TubERLLvcxBxGhFG #sequencenumber{fill:#333}#mermaid-svg-TubERLLvcxBxGhFG #crosshead path{fill:#333;stroke:#333}#mermaid-svg-TubERLLvcxBxGhFG .messageText{fill:#333;stroke:#333}#mermaid-svg-TubERLLvcxBxGhFG .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-TubERLLvcxBxGhFG .labelText,#mermaid-svg-TubERLLvcxBxGhFG .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-TubERLLvcxBxGhFG .loopText,#mermaid-svg-TubERLLvcxBxGhFG .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-TubERLLvcxBxGhFG .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-TubERLLvcxBxGhFG .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-TubERLLvcxBxGhFG .noteText,#mermaid-svg-TubERLLvcxBxGhFG .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-TubERLLvcxBxGhFG .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-TubERLLvcxBxGhFG .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-TubERLLvcxBxGhFG .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-TubERLLvcxBxGhFG .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-TubERLLvcxBxGhFG .section{stroke:none;opacity:0.2}#mermaid-svg-TubERLLvcxBxGhFG .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-TubERLLvcxBxGhFG .section2{fill:#fff400}#mermaid-svg-TubERLLvcxBxGhFG .section1,#mermaid-svg-TubERLLvcxBxGhFG .section3{fill:#fff;opacity:0.2}#mermaid-svg-TubERLLvcxBxGhFG .sectionTitle0{fill:#333}#mermaid-svg-TubERLLvcxBxGhFG .sectionTitle1{fill:#333}#mermaid-svg-TubERLLvcxBxGhFG .sectionTitle2{fill:#333}#mermaid-svg-TubERLLvcxBxGhFG .sectionTitle3{fill:#333}#mermaid-svg-TubERLLvcxBxGhFG .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-TubERLLvcxBxGhFG .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-TubERLLvcxBxGhFG .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-TubERLLvcxBxGhFG .grid path{stroke-width:0}#mermaid-svg-TubERLLvcxBxGhFG .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-TubERLLvcxBxGhFG .task{stroke-width:2}#mermaid-svg-TubERLLvcxBxGhFG .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-TubERLLvcxBxGhFG .taskText:not([font-size]){font-size:11px}#mermaid-svg-TubERLLvcxBxGhFG .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-TubERLLvcxBxGhFG .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-TubERLLvcxBxGhFG .task.clickable{cursor:pointer}#mermaid-svg-TubERLLvcxBxGhFG .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-TubERLLvcxBxGhFG .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-TubERLLvcxBxGhFG .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-TubERLLvcxBxGhFG .taskText0,#mermaid-svg-TubERLLvcxBxGhFG .taskText1,#mermaid-svg-TubERLLvcxBxGhFG .taskText2,#mermaid-svg-TubERLLvcxBxGhFG .taskText3{fill:#fff}#mermaid-svg-TubERLLvcxBxGhFG .task0,#mermaid-svg-TubERLLvcxBxGhFG .task1,#mermaid-svg-TubERLLvcxBxGhFG .task2,#mermaid-svg-TubERLLvcxBxGhFG .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-TubERLLvcxBxGhFG .taskTextOutside0,#mermaid-svg-TubERLLvcxBxGhFG .taskTextOutside2{fill:#000}#mermaid-svg-TubERLLvcxBxGhFG .taskTextOutside1,#mermaid-svg-TubERLLvcxBxGhFG .taskTextOutside3{fill:#000}#mermaid-svg-TubERLLvcxBxGhFG .active0,#mermaid-svg-TubERLLvcxBxGhFG .active1,#mermaid-svg-TubERLLvcxBxGhFG .active2,#mermaid-svg-TubERLLvcxBxGhFG .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-TubERLLvcxBxGhFG .activeText0,#mermaid-svg-TubERLLvcxBxGhFG .activeText1,#mermaid-svg-TubERLLvcxBxGhFG .activeText2,#mermaid-svg-TubERLLvcxBxGhFG .activeText3{fill:#000 !important}#mermaid-svg-TubERLLvcxBxGhFG .done0,#mermaid-svg-TubERLLvcxBxGhFG .done1,#mermaid-svg-TubERLLvcxBxGhFG .done2,#mermaid-svg-TubERLLvcxBxGhFG .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-TubERLLvcxBxGhFG .doneText0,#mermaid-svg-TubERLLvcxBxGhFG .doneText1,#mermaid-svg-TubERLLvcxBxGhFG .doneText2,#mermaid-svg-TubERLLvcxBxGhFG .doneText3{fill:#000 !important}#mermaid-svg-TubERLLvcxBxGhFG .crit0,#mermaid-svg-TubERLLvcxBxGhFG .crit1,#mermaid-svg-TubERLLvcxBxGhFG .crit2,#mermaid-svg-TubERLLvcxBxGhFG .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-TubERLLvcxBxGhFG .activeCrit0,#mermaid-svg-TubERLLvcxBxGhFG .activeCrit1,#mermaid-svg-TubERLLvcxBxGhFG .activeCrit2,#mermaid-svg-TubERLLvcxBxGhFG .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-TubERLLvcxBxGhFG .doneCrit0,#mermaid-svg-TubERLLvcxBxGhFG .doneCrit1,#mermaid-svg-TubERLLvcxBxGhFG .doneCrit2,#mermaid-svg-TubERLLvcxBxGhFG .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-TubERLLvcxBxGhFG .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-TubERLLvcxBxGhFG .milestoneText{font-style:italic}#mermaid-svg-TubERLLvcxBxGhFG .doneCritText0,#mermaid-svg-TubERLLvcxBxGhFG .doneCritText1,#mermaid-svg-TubERLLvcxBxGhFG .doneCritText2,#mermaid-svg-TubERLLvcxBxGhFG .doneCritText3{fill:#000 !important}#mermaid-svg-TubERLLvcxBxGhFG .activeCritText0,#mermaid-svg-TubERLLvcxBxGhFG .activeCritText1,#mermaid-svg-TubERLLvcxBxGhFG .activeCritText2,#mermaid-svg-TubERLLvcxBxGhFG .activeCritText3{fill:#000 !important}#mermaid-svg-TubERLLvcxBxGhFG .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-TubERLLvcxBxGhFG g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-TubERLLvcxBxGhFG g.classGroup text .title{font-weight:bolder}#mermaid-svg-TubERLLvcxBxGhFG g.clickable{cursor:pointer}#mermaid-svg-TubERLLvcxBxGhFG g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-TubERLLvcxBxGhFG g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-TubERLLvcxBxGhFG .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-TubERLLvcxBxGhFG .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-TubERLLvcxBxGhFG .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-TubERLLvcxBxGhFG .dashed-line{stroke-dasharray:3}#mermaid-svg-TubERLLvcxBxGhFG #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-TubERLLvcxBxGhFG #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-TubERLLvcxBxGhFG #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-TubERLLvcxBxGhFG #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-TubERLLvcxBxGhFG #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-TubERLLvcxBxGhFG #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-TubERLLvcxBxGhFG #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-TubERLLvcxBxGhFG #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-TubERLLvcxBxGhFG .commit-id,#mermaid-svg-TubERLLvcxBxGhFG .commit-msg,#mermaid-svg-TubERLLvcxBxGhFG .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-TubERLLvcxBxGhFG .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-TubERLLvcxBxGhFG .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-TubERLLvcxBxGhFG g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-TubERLLvcxBxGhFG g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-TubERLLvcxBxGhFG g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-TubERLLvcxBxGhFG g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-TubERLLvcxBxGhFG g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-TubERLLvcxBxGhFG g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-TubERLLvcxBxGhFG .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-TubERLLvcxBxGhFG .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-TubERLLvcxBxGhFG .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-TubERLLvcxBxGhFG .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-TubERLLvcxBxGhFG .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-TubERLLvcxBxGhFG .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-TubERLLvcxBxGhFG .edgeLabel text{fill:#333}#mermaid-svg-TubERLLvcxBxGhFG .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-TubERLLvcxBxGhFG .node circle.state-start{fill:black;stroke:black}#mermaid-svg-TubERLLvcxBxGhFG .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-TubERLLvcxBxGhFG #statediagram-barbEnd{fill:#9370db}#mermaid-svg-TubERLLvcxBxGhFG .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-TubERLLvcxBxGhFG .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-TubERLLvcxBxGhFG .statediagram-state .divider{stroke:#9370db}#mermaid-svg-TubERLLvcxBxGhFG .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-TubERLLvcxBxGhFG .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-TubERLLvcxBxGhFG .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-TubERLLvcxBxGhFG .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-TubERLLvcxBxGhFG .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-TubERLLvcxBxGhFG .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-TubERLLvcxBxGhFG .note-edge{stroke-dasharray:5}#mermaid-svg-TubERLLvcxBxGhFG .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-TubERLLvcxBxGhFG .error-icon{fill:#522}#mermaid-svg-TubERLLvcxBxGhFG .error-text{fill:#522;stroke:#522}#mermaid-svg-TubERLLvcxBxGhFG .edge-thickness-normal{stroke-width:2px}#mermaid-svg-TubERLLvcxBxGhFG .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-TubERLLvcxBxGhFG .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-TubERLLvcxBxGhFG .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-TubERLLvcxBxGhFG .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-TubERLLvcxBxGhFG .marker{fill:#333}#mermaid-svg-TubERLLvcxBxGhFG .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-TubERLLvcxBxGhFG { color: rgba(0, 0, 0, 0.75); font: ; } DP 状态表示选择集合中前i个元素耗费不超过j的方案属性：Max 计算 (对于第i个元素) f(i,j)=max{f(i-1,j),f(i-1,j-v)+w,f(i-1,j-2v)+2w...}

朴素算法n(o³)

#include<iostream> using namespace std; int n,m; int dp[1010]; int main(){ cin>>n>>m; for(int i=0;i<n;i++){ int v,w; cin>>v>>w; for(int j=m;j>=0;j--){ for(int k=1;k*v<=j;k++){ dp[j]=max(dp[j],dp[j-k*v]+k*w); } } } cout<<dp[m]; }

优化过程：

#mermaid-svg-pB7mnZRdDEuCfxd6 .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 .label text{fill:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 .node rect,#mermaid-svg-pB7mnZRdDEuCfxd6 .node circle,#mermaid-svg-pB7mnZRdDEuCfxd6 .node ellipse,#mermaid-svg-pB7mnZRdDEuCfxd6 .node polygon,#mermaid-svg-pB7mnZRdDEuCfxd6 .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-pB7mnZRdDEuCfxd6 .node .label{text-align:center;fill:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 .node.clickable{cursor:pointer}#mermaid-svg-pB7mnZRdDEuCfxd6 .arrowheadPath{fill:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-pB7mnZRdDEuCfxd6 .flowchart-link{stroke:#333;fill:none}#mermaid-svg-pB7mnZRdDEuCfxd6 .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-pB7mnZRdDEuCfxd6 .edgeLabel rect{opacity:0.9}#mermaid-svg-pB7mnZRdDEuCfxd6 .edgeLabel span{color:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-pB7mnZRdDEuCfxd6 .cluster text{fill:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-pB7mnZRdDEuCfxd6 .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-pB7mnZRdDEuCfxd6 text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-pB7mnZRdDEuCfxd6 .actor-line{stroke:grey}#mermaid-svg-pB7mnZRdDEuCfxd6 .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 .sequenceNumber{fill:#fff}#mermaid-svg-pB7mnZRdDEuCfxd6 #sequencenumber{fill:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 #crosshead path{fill:#333;stroke:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 .messageText{fill:#333;stroke:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-pB7mnZRdDEuCfxd6 .labelText,#mermaid-svg-pB7mnZRdDEuCfxd6 .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-pB7mnZRdDEuCfxd6 .loopText,#mermaid-svg-pB7mnZRdDEuCfxd6 .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-pB7mnZRdDEuCfxd6 .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-pB7mnZRdDEuCfxd6 .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-pB7mnZRdDEuCfxd6 .noteText,#mermaid-svg-pB7mnZRdDEuCfxd6 .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-pB7mnZRdDEuCfxd6 .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-pB7mnZRdDEuCfxd6 .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-pB7mnZRdDEuCfxd6 .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-pB7mnZRdDEuCfxd6 .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-pB7mnZRdDEuCfxd6 .section{stroke:none;opacity:0.2}#mermaid-svg-pB7mnZRdDEuCfxd6 .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-pB7mnZRdDEuCfxd6 .section2{fill:#fff400}#mermaid-svg-pB7mnZRdDEuCfxd6 .section1,#mermaid-svg-pB7mnZRdDEuCfxd6 .section3{fill:#fff;opacity:0.2}#mermaid-svg-pB7mnZRdDEuCfxd6 .sectionTitle0{fill:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 .sectionTitle1{fill:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 .sectionTitle2{fill:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 .sectionTitle3{fill:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-pB7mnZRdDEuCfxd6 .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-pB7mnZRdDEuCfxd6 .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-pB7mnZRdDEuCfxd6 .grid path{stroke-width:0}#mermaid-svg-pB7mnZRdDEuCfxd6 .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-pB7mnZRdDEuCfxd6 .task{stroke-width:2}#mermaid-svg-pB7mnZRdDEuCfxd6 .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-pB7mnZRdDEuCfxd6 .taskText:not([font-size]){font-size:11px}#mermaid-svg-pB7mnZRdDEuCfxd6 .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-pB7mnZRdDEuCfxd6 .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-pB7mnZRdDEuCfxd6 .task.clickable{cursor:pointer}#mermaid-svg-pB7mnZRdDEuCfxd6 .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-pB7mnZRdDEuCfxd6 .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-pB7mnZRdDEuCfxd6 .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-pB7mnZRdDEuCfxd6 .taskText0,#mermaid-svg-pB7mnZRdDEuCfxd6 .taskText1,#mermaid-svg-pB7mnZRdDEuCfxd6 .taskText2,#mermaid-svg-pB7mnZRdDEuCfxd6 .taskText3{fill:#fff}#mermaid-svg-pB7mnZRdDEuCfxd6 .task0,#mermaid-svg-pB7mnZRdDEuCfxd6 .task1,#mermaid-svg-pB7mnZRdDEuCfxd6 .task2,#mermaid-svg-pB7mnZRdDEuCfxd6 .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-pB7mnZRdDEuCfxd6 .taskTextOutside0,#mermaid-svg-pB7mnZRdDEuCfxd6 .taskTextOutside2{fill:#000}#mermaid-svg-pB7mnZRdDEuCfxd6 .taskTextOutside1,#mermaid-svg-pB7mnZRdDEuCfxd6 .taskTextOutside3{fill:#000}#mermaid-svg-pB7mnZRdDEuCfxd6 .active0,#mermaid-svg-pB7mnZRdDEuCfxd6 .active1,#mermaid-svg-pB7mnZRdDEuCfxd6 .active2,#mermaid-svg-pB7mnZRdDEuCfxd6 .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-pB7mnZRdDEuCfxd6 .activeText0,#mermaid-svg-pB7mnZRdDEuCfxd6 .activeText1,#mermaid-svg-pB7mnZRdDEuCfxd6 .activeText2,#mermaid-svg-pB7mnZRdDEuCfxd6 .activeText3{fill:#000 !important}#mermaid-svg-pB7mnZRdDEuCfxd6 .done0,#mermaid-svg-pB7mnZRdDEuCfxd6 .done1,#mermaid-svg-pB7mnZRdDEuCfxd6 .done2,#mermaid-svg-pB7mnZRdDEuCfxd6 .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-pB7mnZRdDEuCfxd6 .doneText0,#mermaid-svg-pB7mnZRdDEuCfxd6 .doneText1,#mermaid-svg-pB7mnZRdDEuCfxd6 .doneText2,#mermaid-svg-pB7mnZRdDEuCfxd6 .doneText3{fill:#000 !important}#mermaid-svg-pB7mnZRdDEuCfxd6 .crit0,#mermaid-svg-pB7mnZRdDEuCfxd6 .crit1,#mermaid-svg-pB7mnZRdDEuCfxd6 .crit2,#mermaid-svg-pB7mnZRdDEuCfxd6 .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-pB7mnZRdDEuCfxd6 .activeCrit0,#mermaid-svg-pB7mnZRdDEuCfxd6 .activeCrit1,#mermaid-svg-pB7mnZRdDEuCfxd6 .activeCrit2,#mermaid-svg-pB7mnZRdDEuCfxd6 .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-pB7mnZRdDEuCfxd6 .doneCrit0,#mermaid-svg-pB7mnZRdDEuCfxd6 .doneCrit1,#mermaid-svg-pB7mnZRdDEuCfxd6 .doneCrit2,#mermaid-svg-pB7mnZRdDEuCfxd6 .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-pB7mnZRdDEuCfxd6 .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-pB7mnZRdDEuCfxd6 .milestoneText{font-style:italic}#mermaid-svg-pB7mnZRdDEuCfxd6 .doneCritText0,#mermaid-svg-pB7mnZRdDEuCfxd6 .doneCritText1,#mermaid-svg-pB7mnZRdDEuCfxd6 .doneCritText2,#mermaid-svg-pB7mnZRdDEuCfxd6 .doneCritText3{fill:#000 !important}#mermaid-svg-pB7mnZRdDEuCfxd6 .activeCritText0,#mermaid-svg-pB7mnZRdDEuCfxd6 .activeCritText1,#mermaid-svg-pB7mnZRdDEuCfxd6 .activeCritText2,#mermaid-svg-pB7mnZRdDEuCfxd6 .activeCritText3{fill:#000 !important}#mermaid-svg-pB7mnZRdDEuCfxd6 .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-pB7mnZRdDEuCfxd6 g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-pB7mnZRdDEuCfxd6 g.classGroup text .title{font-weight:bolder}#mermaid-svg-pB7mnZRdDEuCfxd6 g.clickable{cursor:pointer}#mermaid-svg-pB7mnZRdDEuCfxd6 g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-pB7mnZRdDEuCfxd6 g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-pB7mnZRdDEuCfxd6 .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-pB7mnZRdDEuCfxd6 .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-pB7mnZRdDEuCfxd6 .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-pB7mnZRdDEuCfxd6 .dashed-line{stroke-dasharray:3}#mermaid-svg-pB7mnZRdDEuCfxd6 #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-pB7mnZRdDEuCfxd6 #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-pB7mnZRdDEuCfxd6 #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-pB7mnZRdDEuCfxd6 #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-pB7mnZRdDEuCfxd6 #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-pB7mnZRdDEuCfxd6 #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-pB7mnZRdDEuCfxd6 #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-pB7mnZRdDEuCfxd6 #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-pB7mnZRdDEuCfxd6 .commit-id,#mermaid-svg-pB7mnZRdDEuCfxd6 .commit-msg,#mermaid-svg-pB7mnZRdDEuCfxd6 .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-pB7mnZRdDEuCfxd6 .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-pB7mnZRdDEuCfxd6 .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-pB7mnZRdDEuCfxd6 g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-pB7mnZRdDEuCfxd6 g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-pB7mnZRdDEuCfxd6 g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-pB7mnZRdDEuCfxd6 g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-pB7mnZRdDEuCfxd6 g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-pB7mnZRdDEuCfxd6 .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-pB7mnZRdDEuCfxd6 .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-pB7mnZRdDEuCfxd6 .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-pB7mnZRdDEuCfxd6 .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-pB7mnZRdDEuCfxd6 .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-pB7mnZRdDEuCfxd6 .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-pB7mnZRdDEuCfxd6 .edgeLabel text{fill:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-pB7mnZRdDEuCfxd6 .node circle.state-start{fill:black;stroke:black}#mermaid-svg-pB7mnZRdDEuCfxd6 .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-pB7mnZRdDEuCfxd6 #statediagram-barbEnd{fill:#9370db}#mermaid-svg-pB7mnZRdDEuCfxd6 .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-pB7mnZRdDEuCfxd6 .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-pB7mnZRdDEuCfxd6 .statediagram-state .divider{stroke:#9370db}#mermaid-svg-pB7mnZRdDEuCfxd6 .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-pB7mnZRdDEuCfxd6 .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-pB7mnZRdDEuCfxd6 .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-pB7mnZRdDEuCfxd6 .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-pB7mnZRdDEuCfxd6 .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-pB7mnZRdDEuCfxd6 .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-pB7mnZRdDEuCfxd6 .note-edge{stroke-dasharray:5}#mermaid-svg-pB7mnZRdDEuCfxd6 .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-pB7mnZRdDEuCfxd6 .error-icon{fill:#522}#mermaid-svg-pB7mnZRdDEuCfxd6 .error-text{fill:#522;stroke:#522}#mermaid-svg-pB7mnZRdDEuCfxd6 .edge-thickness-normal{stroke-width:2px}#mermaid-svg-pB7mnZRdDEuCfxd6 .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-pB7mnZRdDEuCfxd6 .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-pB7mnZRdDEuCfxd6 .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-pB7mnZRdDEuCfxd6 .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-pB7mnZRdDEuCfxd6 .marker{fill:#333}#mermaid-svg-pB7mnZRdDEuCfxd6 .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-pB7mnZRdDEuCfxd6 { color: rgba(0, 0, 0, 0.75); font: ; } f(i,j)=max{f(i-1,j),f(i-1,j-v)+w,f(i-1,j-2v)+2w……} f(i,j-v)=max{f(i-1,j-v),f(i-1,j-2v)+w,f(i-1,j-3v)+2w...} f(i,j)=max{f(i-1,j),f(i,j-v)+w}

优化算法：

#include<iostream> using namespace std; int n,m; int v[1010],w[1010]; int dp[1010]; int main(){ cin>>n>>m; for(int i=0;i<n;i++) cin>>v[i]>>w[i]; for(int i=0;i<n;i++){ for(int j=0;j<=m;j++){//这里需要的是dp[i][j-vi],所以从前往后遍历 if(j>=v[i])dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } } cout<<dp[m]; }

最新回复(0)