Dynamic programming infinite knapsack problem

The knapsack problem of infinite items. There are nn items, each of which has an infinite number. Item i has a volume of ViVi and a weight of WiWi. Select some items to put into a backpack with CC capacity, so that the weight of the items in the backpack is as large as possible under the premise that the total volume does not exceed CC.

Memory search method:

#define INF 100

#include<algorithm>
#include<iostream>
using namespace std;

int c = 10,n=3;
int d[INF];  //d[s] represents the maximum weight of this volume
int v[3] = { 1,3,5 };
int w[3] = { 1,7,8 };

int dp(int s)
{
	int i;
	if (d[s] != -1) {
		return d[s];
	}
	d[s] = 0;
	for (i = 0; i < n; i++) {
		if (s >= v[i]) {
			d[s] = max(d[s], dp(s - v[i]) + w[i]);
		}
	}
	return d[s];
}

void print_ans(int s)
{
	int i;
	for (i = 0; i < n; i++) { 
		if (s >= v[i] && (d[s] == d[s - v[i]] + w[i])) {
			cout << v[i] << " ";
			print_ans(s - v[i]);
			break;
		}
	}
}

int main()
{
	memset(d, -1, sizeof(d));
	int i, j,ans=-1;
	for (i = 0; i < n; i++) {
		d[c] = max(d[c], dp(c-v[i])+ w[i]);
	}
	cout <<"The maximum weight that can be loaded is:"<< d[c] <<endl;
	cout << "Type of packing volume:"; print_ans(c);
	return 0;
}

Results:

 

Another is the recursive method, which prints the minimum dictionary order time in exchange for time. It is mentioned in the coin section

#define INF 100

#include<algorithm>
#include<iostream>
using namespace std;

int c = 10,n=3;  //c is volume.
int maxw[INF];  // maxw[s] represents the maximum weight of this volume
int maxw_coin[INF];
int v[3] = { 1,3,5 };
int w[3] = { 1,7,8 };


void print_ans(int s)
{
	while (s) {
		cout << maxw_coin[s]<<" ";
		s = s - maxw_coin[s];
	}
}

int main()
{
	memset(maxw, -INF, sizeof(maxw));
	maxw[0] = 0;  //Give exit
	int i, j;
	for (i = 1; i <= c; i++) {
		for (j = 0; j < n; j++) {
			if (i >= v[j]) {
				if (maxw[i] < maxw[i - v[j]] + w[j]) {
					maxw[i] = maxw[i - v[j]] + w[j];
					maxw_coin[i] = v[j];  
				}
			}
		}
	}
	cout <<"The maximum weight that can be loaded is:"<< maxw[c] <<endl;
	cout << "Type of packing volume:"; print_ans(c);
	return 0;
}

 

Same result

Posted on Fri, 31 Jan 2020 11:44:06 -0800 by izlik