#include<bits/stdc++.h>
using namespace std;
int n=5,c=13;
int v[100]={0,10,3,4,5,4},p[100]={0,24,2,9,10,9};
int dp[100][100],rec[100][100];
// v[i]数组：第i件商品的体积
// p[i]数组：第i件商品的价值
// dp[i][j]数组：前i件商品在只有j容量的情况下可以拿到的最大价值和
// rec[i][j]数组：前i件商品在只有j容量的情况下可以拿到的最大价值和时，第i件商品是拿了还是没拿
int main(){
	//  输入
	// 初始化
	// 开始递推
	for(int i=1;i<=n;i++){
		for(int j=1;j<=c;j++){
			if(v[i]<=j){
				int p1 = dp[i-1][j-v[i]]+p[i];
				int p2 = dp[i-1][j];
				if(p1>p2){
					dp[i][j]=p1;
					rec[i][j]=1;
				}else{
					dp[i][j]=p2;
					rec[i][j]=0;
				}
			}else{
				dp[i][j]=dp[i-1][j];
				rec[i][j]=0;
			}
		}
	}
	cout<<"dp:"<<endl;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=c;j++){
			cout<<dp[i][j]<<"\t";
		}
		cout<<endl;
	}
	cout<<"rec:"<<endl;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=c;j++){
			cout<<rec[i][j]<<"\t";
		}
		cout<<endl;
	}
	cout<<dp[n][c];
	return 0;
}