一部の動的計画法の問題#
も義冢 OJ からのものです
【USACO3.1.2】総得点#
説明#
学生が私たちの USACO の競技で得る得点が多いほど、私たちは嬉しくなります。私たちは、できるだけ多くの得点を得られるように競技を設計しようとしていますが、あなたの助けが必要です。
私たちは、いくつかの種類から競技の問題を選ぶことができます。ここでの「種類」とは、同じ時間で解決でき、同じ得点を得られる問題の集合を指します。あなたの仕事は、USACO のスタッフに、各「種類」から何問選ぶべきかを伝えるプログラムを書くことです。そうすることで、問題を解くための総時間が競技の規定時間内に収まり、総得点が最大になるようにします。
入力には競技の時間：M、問題の種類数：N が含まれます。以降の各行には、ある「種類」を説明するための 2 つの整数が含まれます：最初の整数はその種類の問題を解くことで得られる得点（1 <= points <= 10000）、2 番目の整数はその種類の問題を解くのに必要な時間（1 <= minutes <= 10000）を示します。あなたのプログラムは、各「種類」から何問選ぶべきかを決定し、競技の時間内に最大の得点を得られるようにします。
任意の「種類」からの問題の数は、非負の数（0 以上）である可能性があります。
入力#
第 1 行：M, N-- 競技の時間と問題の「種類」の数。 第 2-N+1 行：2 つの整数：各「種類」の問題の得点と所要時間。
出力#
単独の行には、与えられた制限内で得られる最大の得点が含まれます。
入力例 1#
300 4
100 60
250 120
120 100
35 20
出力例 1#
605
ヒント#
1 <= M <= 10,000 1 <= N <= 10,000 問題の得点は 1..10000 の範囲内；解答に必要な時間は 1..10000 の範囲内
考え方#
完全なナップサック問題、順に埋めていく
i：前i問を考慮
j：総時間
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=10000+5;
struct js{
int tm,mark;
};
int n,m;
js a[MAXN];
int f[MAXN];
int main(){
cin>>m>>n;
for(int i=1;i<=n;++i){
cin>>a[i].mark>>a[i].tm;
}
f[0]=0;
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
if(i-a[j].tm>=0){
if(f[i-a[j].tm]+a[j].mark>f[i]){
f[i]=f[i-a[j].tm]+a[j].mark;
}
}
}
}
cout<<f[m]<<endl;
return 0;
}
【練習問題】言うべきことを言う#
説明#
あなたはもう我慢できませんでした。今こそ、みんなに対するあなたの意見を言う時です。
あなたが n 人に意見を言うと、i 番目の人に話した後、あなたの健康指数は g [i] 減少し、あなたの幸福指数は h [i] 増加します。あなたは各人に最大 1 回話すことができ、特定の順序に従う必要はありません。
あなたの目標は、できるだけ多くの幸福を得ることです。あなたの初期の健康指数は 1000 で、幸福指数は 0 です。もしあなたの健康指数が 0 または負数になった場合、どんなに多くの幸福を得ても、あなたは苦しんで死ぬだけです。
今、あなたが得られる最大の幸福指数を計算するプログラムを書いてください。
入力#
第 1 行：1 つの正整数 N、N 人がいることを示します。 第 2 行：N 個の整数、i 番目の整数はあなたが i 番目の人に話すことで失う健康指数 g [i] を示します。 第 3 行：N 個の整数、i 番目の整数はあなたが i 番目の人に話すことで得られる幸福指数 h [i] を示します。
出力#
出力は 1 行、1 つの整数で、あなたが得られる最大の幸福指数を示します。
入力例 1#
3
10 210 790
200 300 250
出力例 1#
500
ヒント#
30% のデータに対して：1<=N<=20 100% のデータに対して：1<=N<=200 すべてのデータに 0 が含まれています
考え方#
0/1ナップサック、逆から埋める
i番目の人
j: 減少する健康度
#include<cstdio>
#include<cstring>
#include<iostream>
#define max(a,b) (a>b)?(a):(b)
#define fuck(a,b,c) for(int a=b;a<=c;++a)
#define shit(a,b,c) for(int a=b;a>=c;--a)
using namespace std;
const int MAXN=200+5;
int f[1005];
int g[MAXN],h[MAXN];
int n;
int main(){
cin>>n;
memset(f,0,sizeof(f));
fuck(i,1,n){
cin>>g[i];
}
fuck(i,1,n){
cin>>h[i];
}
fuck(i,1,n){
shit(j,1000,1){
if(j-g[i]>0){
f[j]=max(f[j],f[j-g[i]]+h[i]);
}
}
}
cout<<f[1000]<<endl;
return 0;
}
PS#
この設定は奇妙すぎる。。。
人に自分の意見を言ったら、殴られて健康が減る。。。
（コードは少し冗談を言っただけです）
【練習問題】最大の約数の和#
説明#
S を超えないいくつかの異なる正整数を選び、すべての数の約数（自身を除く）の和を最大にします！
入力#
整数 S。
出力#
最大の約数の和を出力します。
入力例 1#
11
出力例 1#
9
ヒント#
30% のデータに対して：S<=10 100% のデータに対して：S<=1000
考え方#
感謝
Perisino大佬（第二の考え方を提供してくれた）
s[i]はiの約数の和を示します
私の考え方#
元々はこう考えていました：
f[第i個数][それらの和]=それらの約数の和;
f[i][j]=max(f[i-1][j-i]+s[i],f[i-1][j]);
そして間違っていることに気づきました
その後、Perisino大佬の方法に修正し、約数の和を求める関数が間違っていることに気づきました。
ここでの約数の和は自身を含まず、私は最初に自身を加えてしまいました
その後、正しいことがわかりました
素晴らしいです～
#include<cstdio>
#include<queue>
#include<iostream>
using namespace std;
const int MAXN=1005;
deque<int> ys[MAXN];
deque<int> s;
int f[MAXN];
int yueshuhe(int x);
int main(){
int he;
cin>>he;
yueshuhe(he);
for(int i=1;i<=he;++i){
for(int j=i;j<=he;++j){
f[j]=max(f[j-i]+s[i],f[j]);
}
}
cout<<f[he]<<endl;
return 0;
}
int yueshuhe(int x){
s.resize(x+5);
for(int i=1;i<=x;++i){
for(int j=1;j<=x/i;++j){
ys[i*j].push_back(i);
s[i*j]+=i;
}
s[i]-=i;
}
}
Perisino 大佬の考え方#
f[i]=max(f[i],s[j]+f[i-j]);
外側：和がi
内側：jと選ばれた数の合計=i
なので
for(int i=1;i<=he;++i){
for(int j=1;j<=i;++j){
f[i]=max(f[i],f[i-j]+s[j]);
}
}
PS：
? 大佬の原版コードは、求めたs配列の上でdpを行うので、私は一瞬混乱しました。。。
【練習問題】ナップサック問題 [4]#
説明#
問題 1: ナップサックを満たす
N 個の物品が与えられ、i 番目の物品の体積は v [i]、価値は p [i] です。容量 C のナップサックを満たすために、いくつかの物品を選び、得られる最大の価値を求めます。満たせない場合は - 1 を出力します。
問題 2ナップサック
N 個の物品が与えられ、i 番目の物品の体積は v [i]、価値は p [i] です。容量 C のナップサックに K 個を選び入れるために、得られる最大の価値を求めます。解がない場合は - 1 を出力します。
入力#
第 1 行：2 つの整数 C と N。
? 次の N 行：各行 2 つの整数、v [i] と p [i] を示します。
? 最後の行、整数 K（問題 2 に対して）。
出力#
第 1 行：問題 1 の解を示す整数、満たせない場合は - 1 を出力します。 第 2 行：問題 2 の解を示す整数、解がない場合は - 1 を出力します。
入力例#
【例1】
10 5
2 2
8 7
3 3
5 4
7 8
3
【例2】
10 5
2 2
8 7
3 3
5 4
7 8
4
【例3】
16 5
3 3
1 3
2 1
5 4
4 6
3
出力例#
【例1】
11
9
【例2】
11
-1
【例3】
-1
13
ヒント#
1<=K<=N<=100 1<=v[i]<=C<=20000 1<=p[i]<=1,000,000
考え方#
問題 1 については、0 以降の項を-infに初期化すればよいです
問題 2 については、私は混乱しています
そして、dyx 大佬が AC コードを共有してくれたことに感謝し、この問題の本質を体験しました
f[i][j][l]=max(f[i-1][j][l],f[i-1][j-1][l-v[i]]+p[i]);
ここで
iは物品の数
jは選択した物品の数
lはナップサックの占有容量
空間を2次元に圧縮（0/1ナップサックを逆から埋める）：
for(int i=1;i<=n;++i){
for(int j=k;j>=1;--j){
for(int l=c;l>=v[i];--l){
f2[j][l]=max(f2[j][l],f2[j-1][l-v[i]]+p[i]);
}
}
}
完全なコード：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=105,MAXC=2e4+5,INF=0x3f3f3f3f;
int v[MAXN],p[MAXN];
int f1[MAXC],f2[MAXN][MAXC];
int n,c,k;
int main(){
cin>>c>>n;
for(int i=1;i<=n;++i){
cin>>v[i]>>p[i];
}
cin>>k;
for(int j=1;j<=c;++j){
f1[j]=-INF;
}
for(int i=1;i<=n;++i){
for(int j=c;j>=v[i];--j){
f1[j]=max(f1[j],f1[j-v[i]]+p[i]);
}
}
for(int i=1;i<=n;++i){
for(int j=k;j>=1;--j){
for(int l=c;l>=v[i];--l){
f2[j][l]=max(f2[j][l],f2[j-1][l-v[i]]+p[i]);
}
}
}
cout<<(f1[c]<0?-1:f1[c])<<endl<<(f2[k][c]?f2[k][c]:-1)<<endl;;
return 0;
}
PS：
私はずっと k が k 個のナップサックを満たすためのものであると思っていました。実際、これが私がずっと解けなかった理由です
そのため、私はこのような問題解決のための解答を探しました。。。
恥ずかしい！