背包问题扩展二.cpp

来自「这是经典的背包问题」· C++ 代码 · 共 53 行

#define MAX 100000
#include<iostream>
using namespace std;

int Packet(int *Weight, int *Value, int n, int Capacity);

int main(){
	int n;
	cout<<"Please input the number of things: ";                                       //输入物品总数
	cin>>n;
	int *Weight = new int[n];                                                          //动态申请重量以及价值的内存空间
	int *Value = new int[n];
	
	int Capacity;
	cout<<endl<<"Please input the capacity of bag: ";                                  //输入背包的载重量
	cin>>Capacity;
	
	cout<<endl<<"Please input each thing's weight and its value: ";        
	for (int i=0; i<n; i++)                                                            //依次输入每个物品的重量和价值
		cin>>Weight[i]>>Value[i];
	cout<<endl;

	cout<<"The largest value is: "<<Packet(Weight, Value, n, Capacity)<<endl;
	delete Weight;
	delete Value;
	return 0;
}

int Packet(int *Weight, int *Value, int n, int Capacity){
	int i, j;
	int optp[MAX][MAX];                                                               //用于动态规划的数组，其 optp[i+1][j+1] 表示的是 i 个物体装入容量为 j 的背包的最大价值
	for (i=0; i<=n; i++)
		optp[i][0]=0;                                                                 //对于容量为0的背包，能达到的价值始终为0
	for (i=0; i<=Capacity; i++)
		optp[0][i]=0;                                                                 //把 0 个物体装入任意容量的背包中，价值始终为0
	for (i=0; i<=n; i++){
		for (j=0; j<=Capacity; j++){
			if ((j>=Weight[i]) && (optp[i-1][j-Weight[i]] + Value[i]) > optp[i-1][j])
				optp[i][j] = optp[i-1][j-Weight[i]]+Value[i];
			else
				optp[i][j] = optp[i-1][j];
		}
	}
	j=Capacity;
	for (i=n; i>=0; i--){
		if (optp[i][j] > optp[i-1][j]){
			j -= Weight[i];
		}
	}
	int MaxValue = optp[n][Capacity];
	return MaxValue;
}