Commit35444fd

committed

update 背包问题理论基础完全背包 java代码

1 parent1da6ff7 commit35444fdCopy full SHA for 35444fd

File tree

+40

-1

lines changed

+40

-1

lines changed

Lines changed: 40 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -176,9 +176,48 @@ int main() {`
`176`	`176`
`177`	`177`	`##其他语言版本`
`178`	`178`
`179`		`-`
`180`	`179`	`Java：`
`181`	`180`
	`181`	+```java
	`182`	`+//先遍历物品，再遍历背包`
	`183`	`+privatestaticvoid testCompletePack(){`
	`184`	`+int[] weight= {1,3,4};`
	`185`	`+int[] value= {15,20,30};`
	`186`	`+int bagWeight=4;`
	`187`	`+int[] dp=newint[bagWeight+1];`
	`188`	`+for (int i=0; i< weight.length; i++){`
	`189`	`+for (int j=1; j<= bagWeight; j++){`
	`190`	`+if (j- weight[i]>=0){`
	`191`	`+ dp[j]=Math.max(dp[j], dp[j- weight[i]]+ value[i]);`
	`192`	`+ }`
	`193`	`+ }`
	`194`	`+ }`
	`195`	`+for (int maxValue: dp){`
	`196`	`+System.out.println(maxValue+"");`
	`197`	`+ }`
	`198`	`+ }`
	`199`	`+`
	`200`	`+//先遍历背包，再遍历物品`
	`201`	`+privatestaticvoid testCompletePackAnotherWay(){`
	`202`	`+int[] weight= {1,3,4};`
	`203`	`+int[] value= {15,20,30};`
	`204`	`+int bagWeight=4;`
	`205`	`+int[] dp=newint[bagWeight+1];`
	`206`	`+for (int i=1; i<= bagWeight; i++){`
	`207`	`+for (int j=0; j< weight.length; j++){`
	`208`	`+if (i- weight[j]>=0){`
	`209`	`+ dp[i]=Math.max(dp[i], dp[i- weight[j]]+ value[j]);`
	`210`	`+ }`
	`211`	`+ }`
	`212`	`+ }`
	`213`	`+for (int maxValue: dp){`
	`214`	`+System.out.println(maxValue+"");`
	`215`	`+ }`
	`216`	`+ }`
	`217`	+```
	`218`	`+`
	`219`	`+`
	`220`	`+`
`182`	`221`	`Python：`
`183`	`222`
`184`	`223`	```python3

Comments

(0)