细细品味背包问题之一

追梦少年_66

[Asm] 纯文本查看 复制代码

/*背包问题是可以用动态规划解决的经典问题。如果你从未了解过动态规划，从未了解过背包问题，理解这一系列文章将是一个痛苦的过程。因为它非常的抽象。

真正的理解后，你就会发现动态规划这一思想的强大之处。编程真正改变自己的思维方式，这就叫顿悟的快乐
附件是颇有影响力的背包问题九讲，非常有意思。

这一讲带来经典的背包问题之0-1背包，这是理解后面完全背包，多重背包的基础。

【0-1背包的描述】
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。


【0-1背包问题的思路】
#define count 5 //物品数量
#define weight 10//背包重量为10

int a[count][weight+1] = { 0 }; //二维数组，wight+1是让0废弃。a[i][j] 代表j重量下，只包含i物品...到count物品的最大价值
int w[count] = { 2,2,6,5,4 };//w[i]代表第i中物品的重量
int v[count] = { 6,3,5,4,6 };//        v[i]代表弟i种物品价值

背包物体的思路：考虑a[i][j]的价值，即j重量下只包含第i种物品...到最后一件物品的最大价值

1、如果包含了第i种商品，则剩余重量为j-w[j] 问题转化为j-w[j]重量下只包含第i+1种物品...到最后一件物品的最大价值

2、如果不包含第i种商品，问题转化为j重量下只包含第i+1种物品...到最后一件物品的最大价值

我就将问题转化为了2个子问题，子问题又转为子问题，最后的子问题变为了，在重量为k下，最后一种物品的最大价值。

问题的层层分解，如果子过程是稳健的，那么母问题一定是稳健的，这就是动态规划的精髓。







【0-1背包问题的实现之一二维数组】
二维数组的方式
这是一种最好的理解的入门方式。请参考此帖子的思路过程，一步一步的教你很详细http://blog.csdn.net/dapengbusi/article/details/7463968
此方法虽然占用了很多的空间，但是他确实保留了所有的计算过程。这种方式能够很快的求出最优解。
*/
#include<stdio.h>
#include<stdlib.h>

#define count 5 //物品数量
#define weight 10//背包重量为10


int a[count][weight+1] = { 0 }; //二维数组，wight+1是让0废弃。a[i][j] 代表j重量下，只包含i物品...到count物品的最大价值
int w[count] = { 2,2,6,5,4 };//w[i]代表第i中物品的重量
int v[count] = { 6,3,5,4,6 };//        v[i]代表弟i种物品价值
void show() {   //打印当前状态
        for (int i = 0; i <count; i++) {
                for (int j = 0; j <weight+1; j++) {
                        printf("%2d,", a[i][j]);
                }
                printf("\n");
        }
        printf("\n-------------------------\n");
}

void main() {


        //初始化最后一行
        for (int j = 10; j > 0; j--) {
                if (j >= w[count - 1]) {
                        a[count - 1][j] = v[count - 1];
                }
                else {
                        a[count - 1][j] = 0;
                }        
        }

        //不在最后一行对比a[i+1][j - w[i]] + v[i]，a[i+1][j]大小。
        //a[i+1][j] ：是j重量下不包含i物品的后几种物品的最大价值。
        //a[i+1][j - w[i]] + v[i] ：包含了第i种物品的最大价值。如果我打算包含i物品，则包含i物体后剩余重量为j - w[i],而在剩余重量为j - w[i]情况下，后几种物品的最大价值为a[i+1][j - w[i]]
        for (int i = count-2; i >=0; i--) {
                for (int j = weight; j >0; j--) {
                                if (j >= w[i]) {//剩余背包重要大于当前物品重量
                                        a[i][j] = a[i+1][j - w[i]] + v[i] > a[i+1][j] ? a[i+1][j - w[i]] + v[i] : a[i+ 1][j];
                                }
                                else {
                                        a[i][j] = a[i+1][j];
                                }        
                }
                show();
        }
}




【0-1背包问题求最优解】
最优解就是一个相反的过程，通过最后一个最优过程推前一个最优过程，你可以将下面的代码附后就可求出最优解

int tempweight = 10;


        //求最优解
        printf("最优解为------------------\n");
        for (int i = 0; i <=count-2; i++) {
                for (int j = weight; j > 0; j++) {

                }
                if (a[i][tempweight] == a[i + 1][tempweight]) { //是否最优解有此物品？

                }
                else {
                        printf("%d\n", i);
                        tempweight -= w[i];
                }
        }
        if (a[count - 1][tempweight] != 0) {  //是否最优解有最后一个物品？
                printf("%d\n", count);
        }





【0-1背包问题实现之二：滚动数组】
有一种一维数组就能实现实现的方式，别人都把它叫做滚动数组。其实实现的原理是一样的。代码非常简洁，如果不懂你需要细细的推敲，只要你理解了上面的基础就不难。
这种方式压缩了空间，却带来了不能保存状态的弊病。即此状态不能明确是哪一个状态推倒而来的。但是这种方法仍然是有意义的。

#include<stdio.h>
#include<stdlib.h>

int a[11] = { 0 };//背包重量为10
int w[4] = { 2,4,6,5 };//重量
int v[4] = { 3,4,5,6 };//价值

void show() {
        for (int i = 0; i < 11; i++) {
                printf("%d,",a[i]);
        }
        printf("\n-------------------------\n");
}

void main() {
        show();
        for (int i = 0; i < 4; i++) {
                for (int j = 10; j >0; j--) {  //j从背包重量到1，这里是关键。通过这种方式子问题 a[j - w[i]] + v[i]， a[j]就像二维数组一样任然能够找到
                        if (j- w[i] >= 0) {
                                a[j] = a[j - w[i]] + v[i] > a[j] ? a[j - w[i]] + v[i] : a[j];
                        }
                }
                show();
        }
        system("pause");
}






【0-1背包问题完全装满】
上面的问题其实都是可以装不满的情况，如果必须要求装满呢？其实非常简单，只需要初始化的时候，将a[j]每一个值变成一个非常大的的负数，就可以解决。为什么？用二维数组来举例子。a[i][j]的子问题a[i+1][j - w[i]] + v[i]，a[i+1][j]如果都是一个很大的数，那么就说明a[i][j]一定是一个垃圾数，垃圾数就意味着重量为j时是装不满的。这里理解的精髓是如果母问题的两个子问题是负数，意味着母问题一定装不满

[mw_shl_code=asm,true]#include<stdio.h>
#include<stdlib.h>

int a[11] = { 0 };//背包重量为10
int w[4] = { 2,4,6,5 };//重量
int v[4] = { 3,4,5,6 };//价值

void show() {
for (int i = 0; i < 11; i++) {
printf("%d,",a[i]);
}
printf("\n-------------------------\n");
}
void main_2x() {//要求装满时只用初始化a数组为一个很大的值就行。如当重要只有5时，只有重量为5的这个元素才有意义，其他的数都会是一个很小的数。
        for (int i = 1; i < 11; i++) { //从1开始，a[0]任然为0；
                a[i] = -1000;
        }
        show();
        for (int i = 0; i < 4; i++) {
                for (int j = 10; j >0; j--) {
                        if (j - w[i] >= 0) {
                                a[j] = a[j - w[i]] + v[i] > a[j] ? a[j - w[i]] + v[i] : a[j];
                        }
                }
                show();
        }
        system("pause");
}[/size][size=2]
【0-1背包问题完全装满之2】[/size]
[size=2]这里介绍一种不同初始化为无穷大的方式，只要你理解了为什么呀无穷大，你就知道为什么可以这样写，我们可以直接跳过负数，如果母问题的两个子问题都是负数，就可以直接跳过，因为母问题一定会是装不满的[/size][size=2]
void main_3x() {
        for (int i = 1; i < 11; i++) { //从1开始，a[0]任然为0；
                a[i] = -1;
        }
        show();
        for (int i = 0; i < 4; i++) {
                for (int j = 10; j >0; j--) {
                        if (j >= w[i]) {//此重量大于当前重量
                                if (a[j] > 0) {//此重量结果有效，有效意味着在此重量下一定能装满
                                        if (a[j - w[i]] >= 0) {//减去当前重量的结果是否有效
                                                a[j] = a[j - w[i]] + v[i] > a[j] ? a[j - w[i]] + v[i] : a[j];
                                        }
                                }
                                else {//说明上一个结果无效
                                        if (a[j - w[i]] >= 0) {
                                                a[j] = a[j - w[i]] + v[i];
                                        }
                                }
                        }
                }
                show();
        }
        system("pause");}[/size][size=2]

17553573

不懂，帮顶

Mcoco

大致意思就是求最优解决方案和利益最大化的一种思路

amw321

不太懂，支持大哥了

追梦少年_66

哥的文章在csdn同步更新http://blog.csdn.net/weixin_39788534/article/details/78866304

starrykirby

DP问题一直很困扰啊，先Mark一下，以后有空再慢慢细读