学习
算法学习——dd大佬：背包九讲（洛谷）
算法学习——dd大佬：背包九讲（博客园）
P236 采药
#include <bits/stdc++.h>
using namespace std;
int t, m;
int f[1005];
int main() {
cin >> t >> m;
for (int i = 1; i <= m; i++) {
int v, w;
cin >> v >> w;
for (int j = t; j >= v; j--)
f[j] = max(f[j], f[j - v] + w);
}
printf("%d\n", f[t]);
return 0;
}
P237 开心的金明
#include <bits/stdc++.h>
using namespace std;
int mon, num, pr[30], mp[30], dp[30005];
int main() {
cin >> mon >> num;
for (int i = 1; i <= num; i++)
cin >> pr[i] >> mp[i];//pr单价，mp单件物品的重要性
for (int i = 1; i <= num; i++)
for (int j = mon; j >= pr[i]; j--)
dp[j] = max(dp[j], dp[j - pr[i]] + pr[i] * mp[i]);
cout << dp[mon];
return 0;
}
//dp[i][j]=max(dp[i][j],dp[i-1][j-pr[i]]+pr[i]*mp[i])
P238 完全背包问题
#include <iostream>
#define ll long long
using namespace std;
ll a[10005], b[10005], c[10005][10005];
int main() {
int n, m;
cin >> m >> n;
for (int i = 1; i <= n; i++)
cin >> a[i] >> b[i];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j < a[i])
c[i][j] = c[i - 1][j];
else
c[i][j] = max(c[i - 1][j], c[i][j - a[i]] + b[i]);
}
}
cout << "max=" << c[n][m];
return 0;
}
P239 竞赛总分
#include <bits/stdc++.h>
using namespace std;
int m, n, i, j;
int s, t, f[10005];
int main() {
cin >> m >> n;
f[0] = 0;
for (i = 1; i <= n; i++) {
cin >> s >> t;
for (j = t; j <= m; j++)
if (f[j - t] + s > f[j])
f[j] = f[j - t] + s;
}
cout << f[m];
return 0;
}
P240 砝码称重
#include <bits/stdc++.h>
using namespace std;
int num[10];
int val[10] = {1, 2, 3, 5, 10, 20}, f[2005] = {0};
int value[2005];
int m, k, ans;
int main() {
for (int i = 0; i < 6; i++) {
cin >> num[i];
m += val[i] * num[i];
}
for (int i = 0; i < 6; i++) {
for (int j = 1; j <= num[i]; j *= 2) {
value[k] = val[i] * j;
num[i] -= j;
k++;
}
if (num[i] != 0) {
value[k] = val[i] * num[i];
k++;
}
}
for (int i = 0; i < k; i++)
for (int j = m; j >= 1; j--)
if (j >= value[i])
f[j] = max(f[j], f[j - value[i]] + value[i]);
for (int i = 1; i <= m; i++)
if (f[i] == i)
ans++;
cout << "Total=" << ans << endl;
return 0;
}
P241 最小乘车费用
#include <bits/stdc++.h>
using namespace std;
int dp[1005];
int n;
int main() {
memset(dp, 0x3f3f3f3f, sizeof dp);
for (int i = 1; i <= 10; i++)
cin >> dp[i];
cin >> n;
for (int i = 2; i <= n; i++)
for (int j = 1; j < i; j++)
dp[i] = min(dp[i], dp[j] + dp[i - j]);
cout << dp[n];
return 0;
}
P242 逃亡的准备
#include<bits/stdc++.h>
using namespace std;
int n,m,v,w,p;
int val[10005];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v>>w>>p;
if(p==0||m/v<=p){
for(int j=v;j<=m;j++)
val[j]=max(val[j],val[j-v]+w);
}
else{
int base=1;
while(p){
p-=base;
int tv=base*v,tw=base*w;
for(int j=m;j>=tv;j--)
val[j]=max(val[j],val[j-tv]+tw);
base*=2;
base=min(base,p);
}
}
}
cout<<val[m];
return 0;
}
//谢谢G，复习了二进制优化
P243 庆功会
#include<bits/stdc++.h>
using namespace std;
int n, m;
int v[100005], w[100005], s[100005];
int val[100005];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
for(int k=1;k<=s[i];k++){
if(k*v[i]>j) break;
val[j]=max(val[j],val[j-v[i]*k]+w[i]*k);
}
}
}
cout<<val[m];
return 0;
}
//dp方程：val[j]=max(val[j],val[j-v[i]*k]+w[i]*j)
//val[j]表示价值
//如果不购买，val[j]=val[j]
//如果购买k个，val[j]=val[j-v[i]*k+w[i]*k
P244 混合背包
#include <bits/stdc++.h>
using namespace std;
int m, n;
int w[35], c[35], p[35];
int f[205];
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++)
cin >> w[i] >> c[i] >> p[i];
for (int i = 1; i <= n; i++)
if (p[i] == 0) {
for (int j = w[i]; j <= m; j++)
f[j] = max(f[j], f[j - w[i]] + c[i]);
} else {
for (int j = 1; j <= p[i]; j++)
for (int k = m; k >= w[i]; k--)
f[k] = max(f[k], f[k - w[i]] + c[i]);
}
cout << f[m];
return 0;
}
P245 NASA的食物计划
#include <bits/stdc++.h>
using namespace std;
int f[405][405] = {0};
int v, m, n, x, y, z;
int main() {
cin >> v >> m >> n;
while (n--) {
cin >> x >> y >> z;
for (int i = v; i >= x; i--)
for (int j = m; j >= y; j--)
f[i][j] = max(f[i][j], f[i - x][j - y] + z);
}
cout << f[v][m];
}
//状态转移方程：f[k][i][j]=max{f[k-1][i][j],f[k-1][i-v[k]][j-m[k]]}
P246 分组背包
#include <bits/stdc++.h>
using namespace std;
int v, n, t; //v背包容量，n物品数量，t组数
int w[35], c[35]; //w[i]物品重量，c[i]物品价值
int bag[15][35], val[205]; //bag[i][j]:物品j在i组中，val[i]:物品价值
int main() {
cin >> v >> n >> t;
for (int i = 1; i <= n; i++) {
int x;
cin >> w[i] >> c[i] >> x;
bag[x][++bag[x][0]] = i;
}
for (int i = 1; i <= t; i++) {
for (int j = v; j >= 0; j--) {
for (int k = 1; k <= bag[i][0]; k++) {
if (j >= w[bag[i][k]]) {
if (val[j] < val[j - w[bag[i][k]]] + c[bag[i][k]]) {
val[j] = val[j - w[bag[i][k]]] + c[bag[i][k]];
}
}
}
}
}
cout << val[v];
return 0;
}
//dp方程：val[j]=max(val[j],val[j-w[bag[i][k]]]+c[bag[i][k]])
P247 新年趣事之打牌
#include <bits/stdc++.h>
using namespace std;
int N, sum, V, cnt;
int w[105], vis[100005], g[100005], ans[105];
int main() {
cin >> V >> N;
for (int i = 1; i <= N; i++) {
cin >> w[i];
sum += w[i];
}
V = sum - V;
g[0] = 1;
for (int i = 1; i <= N; i++) {
for (int j = V; j >= w[i]; j--) {
if (g[j - w[i]]) {
if (!g[j]) vis[j] = i;
g[j] += g[j - w[i]];
}
}
}
if (!g[V]) cout << "0";
else if (g[V] >= 2) cout << "-1";
else if (g[V] == 1) {
for (int i = V; i >= 1; i -= w[vis[i]])
ans[++cnt] = vis[i];
sort(ans + 1, ans + 1 + cnt);
for (int i = 1; i <= cnt; i++)
cout << ans[i] << " ";
}
return 0;
}
P248 积木城堡
#include <bits/stdc++.h>
using namespace std;
int high[10005], v[10005], n, ni, sum, maxsum, a[10005];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
ni = 1;
sum = 0;
cin >> a[ni];
sum += a[ni];
while (a[ni] != -1) {
ni++;
scanf("%d", &a[ni]);
sum += a[ni];
}
ni--;
sum++;
if (sum > maxsum)
maxsum = sum;
for (int j = 1; j <= sum; j++)
v[j] = 0;
v[0] = 1;
for (int j = 1; j <= ni; j++)
for (int k = sum; k >= a[j]; k--)
if (!v[k] && v[k - a[j]]) {
v[k] = 1;
high[k]++;
}
}
for (int i = maxsum; i >= 1; i--)
if (high[i] == n) {
printf("%d", i);
return 0;
}
printf("0");
}