背包问题

问题 A: 背包问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 517  解决: 259
[提交][状态][讨论版]

题目描述

有个背包可承受重量N，现有T类物品 
每类物品重量为Wi,价值为Vi ,每类物品的数量只有一个的, 
这个背包可以装载物品的最大价值是多少?

输入

一行,N T 之间用空格隔开 
后面t行,每行:重量Wi,价值Vi

输出

 

 

这个背包可以装载物品的最大价值

 

样例输入

100 5

77 92

22 22

29 87

50 46

99 90

样例输出

261

 

 

题目分析：这道题目可以通过一条方程和一个表格来协助理解：F[i,v]=maxF[i−1,v],F[i−1,v−Ci]+Wi

这条式子是参考网友的，那么要怎么去理解呢？F[i,V]前i件物品中选择若干件放在容量为v的背包中，可以取得的最大价值。

对于每一个物品来分析，都有放入背包，或者不放入背包两种情况。当不放入背包的时候，
F[i,v]=F[i−1,v]表示前i件物品放入背包的最大价值等于前i-1件物品放入背包所能达到的最大价值，因为第i件并没有放进去，所以背包的价值并不会增加既F[i][v]的价值跟F[i-1][v]的价格是一样的。

若选择放，v−Ci确保有足够的空间，随之F[i,v]=F[i−1,v−Ci]+Wi。其中，F[i-1,v-Ci]代表当恰好能装进第i件物品时的容量所对应的最佳价值。

下列是一组测试数据的表格形式：

static int[] C = { -1, 2, 2, 6, 5, 4 };//代表每件物品的重量，从第1位开始

static int[] W = { -1, 6, 3, 5, 4, 6 };//代表每件物品的价值，从第1位开始

name	weight	value	0	1	2	3	4	5	6	7	8	9	10
a	2	6	0	0	6	6	9	9	12	12	15	15	15
b	2	3	0	0	3	3	6	6	9	9	9	10	11
c	6	5	0	0	0	0	6	6	6	6	6	10	11
d	5	4	0	0	0	0	6	6	6	6	6	10	10
e	4	6	0	0	0	0	6	6	6	6	6	6	6

 

 

代码示例：

package com.eangaie.main.lanqiaobeiDP;

 

/**

*

* @CreateTime 2018年3月14日下午10:40:37

*

* @author谢彦杰

*

* @since JDK 1.8

*

* 文件名称：A.java

*

* 背包问题

*

**/

 

 

public class A {

 

    static final int N = 5;// 物品个数

    static final int V = 10;// 背包体积

    static int[] C = { -1, 2, 2, 6, 5, 4 };

    static int[] W = { -1, 6, 3, 5, 4, 6 }; // 第 i 个物品的价值

    static int[][] F = new int[N + 1][V + 1]; // 模拟一个（背包容量，物品价值）的表格

 

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        int i, j;

        for (i = 1; i <= N; i++) {

            for (j = 0; j <= V; j++) {

                /* 分两种情况讨论，放与不放 */

                F[i][j] = F[i - 1][j];/* 不放时候的价值 */

                /*如果放入这件物品之后的价值大于不放，则选择放入物品*/

                /*C[i] <= j （代表这个物品能装进） && F[i][j] < F[i - 1][j - C[i]]（代表装上一件物品，已经背包空间正好或者大于能装下这件物品的空间时，这个背包的价值） + W[i]（加上这件物品的价值）

                 * 判断，若是价值更大，则保存这个结果*/

                if (C[i] <= j && F[i][j] < F[i - 1][j - C[i]] + W[i]) {

                    F[i][j] = F[i - 1][j - C[i]] + W[i];

                }

 

            }

        }

        System.out.println(F[N][V]);

    }

 

}

 

运行结果：15