背包.cpp

来自「在学习计算算法分析与设计时编写的几个算法代码」· C++ 代码 · 共 43 行

#include"stdio.h"

void knapsack(int v[],int w[],int c, int n,int m[][11])
{
	int jmax=(w[n]-1)>c?c:(w[n]-1);
	for(int j=0;j<=jmax;j++)
		m[n][j]=0;
	for(j=w[n];j<=c;j++)
		m[n][j]=v[n];

	for(int i=n-1;i>=0;i--)
	{

		jmax=(w[i]-1>c)?c:(w[i]-1);
        for(j=0;j<=jmax;j++)
		m[i][j]=m[i+1][j];
    	for(j=w[i];j<=c;j++)
			m[i][j]=m[i+1][j]>(m[i+1][j-w[i]]+v[i])?m[i+1][j]:(m[i+1][j-w[i]]+v[i]);
	}

    m[1][c]=m[2][c];
    if(c>=w[1])
		m[1][c]=m[1][c]>(m[2][c-w[1]]+v[1])?m[1][c]:(m[2][c-w[1]]+v[1]);
}
void main()
{
	int i,j,n,c;
	int v[6]={0,6,3,5,4,6};
	int w[6]={0,2,2,6,5,4};
	
	int m[7][11]={0};
	c=10,n=5;
	knapsack(v,w,c,n,m);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=c;j++)
	    printf("%5d",m[i][j]);
		printf("\n");
	}
}