背包扣

0/1 knapsack

Judy的份扣：

#include <iostream>
#include <math.h>
using namespace std;
#define N 100

/*// 沒有dp, 直接遞迴算
int bp(int n, int i, int v, int w[], int c[]){
	if (i == n)	// 超過了才可以回傳價值0
		return 0;
	else if (v >= w[i])
		return max(c[i] + bp(n, i+1, v-w[i], w, c), bp(n, i+1, v, w, c))
	else if (v > 0)
		return bp(n, i+1, v, w, c);
	else	// 會有v<0的狀況嗎？
		return 0;
}*/

/*// 下填到上，越上面數字越大；左填到右，越右邊數字越大
int bp(int n, int i, int v, int w[], int c[], int dp[][N]){
	if (i == n)	// 超過了才可以回傳價值0
		return 0;
	if (dp[i][v] > 0)
		return dp[i][v];
	if (v >= w[i])
		dp[i][v] =  max(c[i] + bp(n, i+1, v-w[i], w, c, dp), bp(n, i+1, v, w, c, dp));
	else if (v > 0)
		dp[i][v] = bp(n, i+1, v, w, c, dp);
	else	// 會有v<0的狀況嗎？
		return 0;
	return dp[i][v];
}*/

// 上填到下，越下面數字越大；左填到右，越右邊數字越大
int bp(int n, int i, int v, int w[], int c[], int dp[][N]){
	if (i < 0)	// 超過了才可以回傳價值0
		return 0;
	if (dp[i][v] > 0)
		return dp[i][v];
	if (v >= w[i])
		dp[i][v] =  max(c[i] + bp(n, i-1, v-w[i], w, c, dp), bp(n, i-1, v, w, c, dp));
	else if (v > 0)
		dp[i][v] = bp(n, i-1, v, w, c, dp);
	else	// 會有v<0的狀況嗎？
		return 0;
	return dp[i][v];
}

void backtrack(int n, int i, int v, int w[], int c[], int dp[][N]){
	if (i <= 0)
		return;
	else if (dp[i][v] == dp[i][v-1]){
		backtrack(n, i, v-1, w, c, dp);
	} else {
		backtrack(n, i-1, v-w[i], w, c, dp);
		cout << "Take item " << i << " :\tw = " << w[i] << "\tc = " << c[i] << endl;
	}
}

int main(){
	int n, v;
	cin >> n >> v;
	int w[n], c[n], dp[N][N] = {0};
	for(int i = 0; i < n; i++){
		cin >> w[i];
	}
	for(int i = 0; i < n; i++){
		cin >> c[i];
	}
	//cout << bp(n, 0, v, w, c, dp) << endl;
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= v; j++){
			dp[i][j] = bp(n, i, j, w, c, dp);
			cout << dp[i][j] << ((j == v)?"\n":" ");
		}
	}
	backtrack(n, n-1, v, w, c, dp);
	cout << bp(n, n-1, v, w, c, dp) << endl;

	return 0;
}

---

原始遞迴

#include <stdio.h>

int max(int a, int b){
	return (a >= b)?a:b;
}

int Val(int v[], int w[], int n, int Wei){
	if(n == 0)
		return 0;
	//can't get i-th
	if(Wei < w[n])
		return Val(v, w, n-1, Wei);
	return max(Val(v, w, n-1, Wei), Val(v, w, n-1, Wei-w[n]) + v[n]);
}

int Val2(int v[], int w[], int n, int Wei){
	if(Wei < 0)
		return -1e9;
	if(n == 0)
		return 0;

	return max(Val2(v, w, n-1, Wei), Val2(v, w, n-1, Wei-w[n]) + v[n]);
}

int main(){
	int N, Wei;
	int v[1001] = {0}, w[1001] = {0};
	//input
	scanf("%d %d", &Wei, &N);
	for(int i = 1; i <= N; i++){
		scanf("%d %d", &v[i], &w[i]);
	}

	//processing&output
	printf("%d\n", Val(v, w, N, Wei));
	//printf("%d\n", Val2(v, w, N, Wei));

	return 0;
}

Top Down遞迴版

#include <stdio.h>

int Value[501][500001] = {{0}};
int cnt = 0;
int max(int a, int b){
	return (a >= b)?a:b;
}

int Val2(int v[], int w[], int n, int Wei){
	if(Wei < 0){
		return -1e9;
	}
	if(n == 0){
		return 0;
	}
	if(Value[n][Wei] == 0){
		Value[n][Wei] = max(Val2(v, w, n-1, Wei), Val2(v, w, n-1, Wei-w[n]) + v[n]);
		cnt++;
	}
	return Value[n][Wei];
}

int main(){
	int N, Wei;
	int v[501] = {0}, w[501] = {0};
	//input
	scanf("%d %d", &Wei, &N);
	for(int i = 1; i <= N; i++){
		scanf("%d %d", &v[i], &w[i]);
	}

	//processing&output
	printf("%d\n", Val2(v, w, N, Wei));
	printf("%d/%d\n", cnt, N*Wei);	
#ifdef SHOW
	for(int i = 0; i <= N; i++){
		for(int j = 0; j <= Wei; j++){
			printf((j == Wei)?"%2d\n":"%2d ", Value[i][j]);
		}
	}
#endif

	return 0;
}

Bottom up 二維陣列版

#include <stdio.h>

int Value[501][500001] = {{0}};

int max(int a, int b){
	return (a >= b)?a:b;
}

int main(){
	int N, Wei;
	int v[1000] = {0}, w[1000] = {0};
	//input
	scanf("%d %d", &Wei, &N);
	for(int i = 0; i < N; i++){
		scanf("%d %d", &v[i], &w[i]);
	}
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j <= Wei; j++){
			if(j < w[i])
				Value[i+1][j] = Value[i][j];
			else
				Value[i+1][j] = max(Value[i][j], Value[i][j-w[i]] + v[i]);
		}
	}

	//processing&output
	printf("%d\n", Value[N][Wei]);
#ifdef SHOW
	for(int i = 0; i <= N; i++){
		for(int j = 0; j <= Wei; j++){
			printf("%2d%c", Value[i][j], " \n"[j==Wei]);
		}
	}
	printf("\n");
	printf("Optimal Solution:");
	for(int i = N-1, j = Wei; i >= 0; i--){
		if(Value[i+1][j] == Value[i][j-w[i]] + v[i]){
			printf("%d ", i);
			j -= w[i];
		}
	}
	printf("\n");
#endif
	return 0;
}

一維陣列優化

#include <stdio.h>

int Value[5000001] = {0};

int max(int a, int b){
	return (a >= b)?a:b;
}

int main(){
	int N, Wei;
	int v[1000] = {0}, w[1000] = {0};
	//input
	scanf("%d %d", &Wei, &N);
	for(int i = 0; i < N; i++){
		scanf("%d %d", &v[i], &w[i]);
	}

	for(int i = 0; i < N; i++){
		int we = w[i];
		int co = v[i];
		for(int j = Wei; j >= we && j >= 0; j--){
			//printf("%d %d\n", i, j);
			Value[j] = max(Value[j], Value[j-we] + co);
		}
	}

	//processing&output
	printf("%d\n", Value[Wei]);
#ifdef SHOW
	for(int j = 0; j <= Wei; j++){
		printf((j == Wei)?"%2d\n":"%2d ", Value[j]);
	}
#endif

	return 0;
}