学步园

      01背包问题是个老生常谈的关于动态规划的问题。

      首先问题描述：给定n个物品，每个物品的重量是wi，每个物品的价值是pi，背包的最大容量是M，求如何装入这些物品才能使背包里的价值量最大？

      分析：

      假定我们没选择一个物品就是一次决定，0表示不选择这个物品，1表示选择这个物品（这也是01背包问题的来源）。当我们在做第i步决定的时候，我们需要考虑的是在第i-1步决定过后，背包内的剩余容量是否能装下第i个物品，以及这样装入物品是否能使价值量更大。其递归式为：

      s[i][ j] = max{ s[i-1][j] , s[i-1][j-wi]+pi }，当 j >= wi；  s[i][j] = s[i-1][j] ， 当 j < wi；

      s[i][j]表示前 i 个物品，在容量为 j 时所能达到的最大价值量。

     
注：我们理论上应将物品按重量从小到大先排序，这样可以使每个 i， j 的取值时s[i][j]
的结果都合理；当然如果不按从小到大排序，并不影响，当 i
取最大值（总物品数），j  取最大值（ 总背包容量 ）时的结果。

       下面是c语言的具体实现：

文件："h1.h"

#ifndef H1_H
#define H1_H

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<process.h>
#include<math.h>

#define MAXSIZE 100

struct goods{
	int weight;
	int value;
};

void knapsack(goods g[], int n, int m, int s[][MAXSIZE]);
void printGoodsSelected(goods g[], int n, int m, int s[][MAXSIZE]);

#endif

文件："01Knapsack.cpp

#include "h1.h"

 void knapsack(goods g[], int n, int m, int s[][MAXSIZE]){

	int i, j;

	for(i=0; i<=n; i++){
		s[i][0] = 0;
	}

	for(j=1; j<=m; j++){
		s[0][j] = 0;
	}

	for(i=1; i<=n; i++){
		for(j=1; j<=m; j++){
			if(g[i].weight <= j){
				if(s[i-1][j-g[i].weight]+g[i].value > s[i-1][j]){
					s[i][j] = s[i-1][j-g[i].weight]+g[i].value;
				}
				else{
					s[i][j] = s[i-1][j];
				}
			}
			else{
				s[i][j] = s[i-1][j];
			}
		}
	}
 }

 void printGoodsSelected(goods g[], int n, int m, int s[][MAXSIZE]){

	 int i, j;

	 for(i=n, j=m; i>=1; i--){
		 if(s[i][j] > s[i-1][j]){
			 printf("%d   ", i);
			 j = j - g[i].weight;
		 }
	 }
 }

 int main(){

	 int s[MAXSIZE][MAXSIZE];
	 int i;
	 goods  g[4];

	 g[1].weight = 3; g[1].value = 4;
	 g[2].weight = 4; g[2].value = 5;
	 g[3].weight = 5; g[3].value = 6;
    
	 knapsack(g, 3, 10, s);

	 printf("The largest possible value is ：%d\n", s[3][10]);
	 printf("The goods selected:\n");
	 printGoodsSelected(g, 3, 10, s);
	 printf("\n");

	 return 0;
 }

注：上面的测试数据中我们选择了3个物品，重量和价值量分别是：3,4 ；4,5；5,6。背包的容量为10。