糖果
题目 糖果
思路分析
N件产品中 任选若干件 (每件都包含数量不同的糖果）
N个物品 每个物品包含糖果数是他的价值w[i]
希望w[i] 最大 且 为K的整数倍
物品不可拆分 只能选与不选（01背包）
体积无限制
代码实现
dfs （tle）
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;
const int N=110;
int w[N];
int n,k;
int res=0;
void dfs(int u,int sum){
if(u>n){
if(sum%k==0){
res=max(res,sum);
}
return;
}
dfs(u+1,sum+w[u]);
dfs(u+1,sum);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>w[i];
}
dfs(1,0);
cout<<res;
return 0;
}
dp：
不能简单的推f[i]为考虑到第i件物品时 能达到的最大的数量
因为最大的数量不一定是%k==0的最大数量
这样会忽略正确答案
但其实发现它并不是没有体积的限制 限制是关于 %k余数是多少
dp(i,j)代表前i个物品总价值%k=j的集合
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;
const int N=110;
int w[N];
int n,k;
int res=0;
int dp[N][N]; //前i件物品中选 得到价值之和mod k == j时的最大价值和
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>w[i];
}
for(int j=0;j<k;j++) dp[0][j]=-inf; // 一个物品不选 模k==j 为无效状态
dp[0][0]=0; // 一个物品都不选 模 k为 0 和为 0
for(int i=1;i<=n;i++){
// 不选
for(int j=0;j<k;j++){
dp[i][j]=dp[i-1][j];
}
// 选
for(int j=0;j<k;j++){
if(dp[i-1][j]>=0){
int mod = (j+w[i])%k;
dp[i][mod] = max(dp[i][mod],dp[i-1][j]+w[i]);
}
}
}
cout<<dp[n][0];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;
const int N=110;
int w[N];
int n,k;
int res=0;
int dp[N][N]; //前i件物品中选 得到价值之和mod k == j时的最大价值和
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>w[i];
}
for(int j=0;j<k;j++) dp[0][j]=-inf; // 一个物品不选 模k==j 为无效状态
dp[0][0]=0; // 一个物品都不选 模 k为 0 和为 0
for(int i=1;i<=n;i++){
for(int j=0;j<=k-1;j++){
dp[i][j] = max(dp[i - 1][j], dp[i - 1][((j - w[i]) % k + k) % k] + w[i]);
}
}
cout<<dp[n][0];
return 0;
}
💬 评论