基础算法题——younik吃大餐（多重背包）

younik吃大餐

题目描述
Younik的检查结果出来了，核酸检测为阴性，她非常高兴，立刻决定去饭店大吃一顿。到了饭店，Younik看到琳琅满目的菜单，开始犯了选择困难症。这时作为顶级吃货的你恰好坐到了Younik的旁桌，你决定发扬一下雷锋精神，帮助Younik决定吃哪些菜。假设每一道菜都有相应的快乐值，Younik每吃一道菜就会获得相应的快乐值，这里有N道菜，每道菜可以吃多次，但是同一道菜每重复吃一次，得到的快乐值会比原来的快乐值少 2^(k-1) 点（k为重复吃的次数，第一次重复，得到的快乐值会比这道菜的原快乐值少1点，重复第二次时少2点，以此类推）。现在Younik的钱包中有M元，你觉得她可以得到的最大的快乐值是多少呢？

输入描述:
第一行输入N M，表示共有N道菜，小明有M元。接下来的N行，每行有两个数字Wi,Vi，第一个数字表示吃这道菜可得到的快乐值，第二个数字表示这道菜的价格。
菜的标号从1开始。
输出描述:
输出所能得到的最大快乐值

示例1
输入
6 9
3 2
5 2
2 7
1 2
3 3
6 3
输出
18
备注:
0 < N ≤ 100
0 < Vi,Wi ≤ 100
0 < M ≤ 10000

感觉这道题就是从完全背包演化来的，只是在多重背包的基础上需要考虑同种类拿多的情况。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[100010];
struct node{
	ll hap,val; 
}food[110];

ll jc(int x){
	if(x==0) return 0;
	ll ans=1, sum=1;
	for(int i=0; i<x-1; i++){
		ans *= 2;
		sum += ans;
	}
	return sum;
}


int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=0; i<n; i++)
		scanf("%lld%lld", &food[i].hap, &food[i].val);
		
	memset(dp, 0, sizeof(dp));
	for(int j=0; j<n; j++)
	for(int i=m; i>=food[j].val; i--)
	for(int k=1; k*food[j].val<=i&&k*food[j].hap-jc(k-1)>0; k++)
		dp[i] = max(dp[i-k*food[j].val]+k*food[j].hap-jc(k-1), dp[i]);
	
	printf("%lld", dp[m]);
	
	return 0;
} 

完全背包例题