动态规划解0-1背包问题
java 代码<div class="dp-highlighter"><div class="bar" />
[*]/**
[*] *
[*] */
[*]<span />package com.zyf;
[*]
[*]<span />/**
[*] * @author zyf 题目：给定n个物体，其中第i个物体重量wi，价值vi ，另有一个最大载重W的背包，往里面塞东西使得总价值尽可能大
[*] *
[*] * 令f(i,j)表示用前i个物体装出重量为j的组合时的最大价值
[*] * f(i,j)=max{f(i-1,j), f(i-1, j-w)+v } ,i>0, j>=w;
[*] * f(i,j) = f(i-1,j) , i>0, j<w;
[*] * f(0,j) = v , i=0, j>=w;
[*] * f(0,j) = 0, i=0, j<w;
[*] *
[*] */
[*]<span />public class bagPro {
[*]
[*] /**
[*] * @param args
[*] */
[*] public static void main(String[] args) {
[*] // TODO 自动生成方法存根
[*]
[*]
[*] int w[] = {2,2,6,5,4};
[*] int v[] = {6,3,5,4,6};
[*] int c = 10;
[*] int f[][] = new int ;
[*]
[*] int maxValue = 0;
[*]
[*] for(int j=0 ; j<=c; j++){
[*] if(j>=w)
[*] f =v;
[*] else
[*] f = 0;
[*] }
[*]
[*] for(int i=1; i<w.length; i++){
[*] for(int j=0; j<=c;j++){
[*] if(j<w)
[*] f = f;
[*] else if(f>=f]+v)
[*] f = f;
[*] else
[*] f = f]+v;
[*] }
[*] }
[*]
[*] System.out.println(f);
[*]
[*]
[*]
[*]
[*] }
[*]}
页:
[1]