Dynamic Programming

0-1背包问题

有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这是最基础的背包问题.

相当于用f[i][j]表示前i个背包装入容量为v的背包中所可以获得的最大价值。

对于一个物品，只有两种情况

　　情况一: 第i件不放进去，这时所得价值为:f[i-1][j]

　　情况二: 第i件放进去，这时所得价值为：f[i-1][j-w[i]]+c[i] 

状态转移方程为：f[i][j] = max(f[i-1][j], f[i-1][j-w[i]]+v[i])

代码：

import java.util.Scanner;


public class DynamicProgramming01 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        String line0 = sc.nextLine();
        String[] sline = line0.split(" ");
        // for(String k:sline)
        int v = Integer.parseInt(sline[0]);
        int n = Integer.parseInt(sline[1]);
        int[] w = new int[n+1];
        int[] c = new int[n+1];
        for (int i = 0; i < n; i++) {
            String line1 = sc.nextLine();
            String[] sl = line1.split(" ");
            w[i] = Integer.parseInt(sl[0]);
            c[i] = Integer.parseInt(sl[1]);
        }
        System.out.println(dynamicProgramming01(w,c,v,n));
        sc.close();
    }
    public static int dynamicProgramming01(int[] w,int[] c,int v,int n) {
        int[][] f=new int[1001][1001];
        for (int i = 0; i < n + 1; i++)
            f[i][0] = 0;
        for (int j = 0; j < v + 1; j++)
            f[0][j] = 0;
        
        
        for(int i=1;i<=n;i++) {
            
            for(int j=1;j<=v;j++) {
                f[i][j]=f[i-1][j];
            }
//            for(int j=0;j+w[i]<=v;j++) {  
////                f[i][j]=Math.max(f[i-1][j], f[i-1][j-w[i]]+c[i]);
//                f[i][j]=Math.max(f[i][j]+c[i], f[i-1][j+w[i]]);
//            }
            
            for(int j=v;j-w[i-1]>=0;j--) {  
            f[i][j]=Math.max(f[i-1][j], f[i-1][j-w[i-1]]+c[i-1]);
            }
        }
//        int ans=0;
//        for(int i=0;i<=n;i++) {
//            for(int j=0;j<=v;j++) {
//            ans=Math.max(ans,f[i][j]);
//            }
//        }
//        return ans;
        return f[n][v];
        
    }
    public static int dynamicProgramming02(int[] w,int[] c,int v,int n) {
        int[] f=new int[1001];
        for(int i=0;i<n;i++) {
            for(int j=v;j>=w[i];j--) {
                f[j]=Math.max(f[j-w[i]]+c[i], f[j]);
            }
        }
        return f[v];
    }

}