C++リュックの問題を解決

に感謝https://blog.csdn.net/Hearthougan/article/details/53869671
1回だけのリュックサック–0-1リュックサック
問題の説明:
N N N個の物品と1個の容量がS S Sのリュックサックがあって、i i i番目の物品の重量はw[i]w[i]w[i]で、価値はv[i]v[i]v[i]です.それぞれの品物を一度だけ置くことができて、分割することができなくて、リュックサックの容量を超えない前提の下で、どのようにリュックサックの総価値を最大にすることができますかを聞きます.
考え方:
f[i][j]f[i][j]f[i][j]f[i][j]を、前のi i i個の物品の中から選択し、容量j j j j jのリュックサックの価値を最大にすると定義した.
i i i番目のアイテムについては、次の2つのケースがあります.
1.物品i i iを置く、このときf[i][j]=f[i−1][j−w[i]+v[i]f[i][j]=f[i−1][j−w[i]+v[i]f[i][j]=f[i−1][j−w[i]+v[i]2.物i i iを置かず、このときf[i][j]=f[i−1][j]f[i][j]=f[i−1][j]f[i][j]=f[i]=f[i−1][j]
以上より,本題の状態遷移方程式は,f[i][j]=m a x f[i−1][j−w[i]+v[i],f[i−1][j]f[i][j]=max{f[i−1][j−w[i]+v[i],f[i−1][j]}f[i][j]=maxf[i−[i]+v[i],f[i−1][j]=maxf[i−1][j−w[i]+v[i],f[i−1][j]である.
疑似コードは次のとおりです.

for 1...n
    for w[i]...s
        f[i][j]=max{
     f[i-1][j-w[i]]+v[i]，f[i-1][j]}

この構想は時間的に最適であるが,空間はO(V)O(V)O(V)に最適化できる.
結局f[i][j]f[i][j]f[i][j]f[i][j]は1行だけ関係があるので、1次元配列だけで保存してみましょう.
この方法は実行できますか.実行可能であるが、j j j jは、古いデータが上書きされないため、逆列挙される.
f[j]f[j]f[j]f[j]はf[j−w[i]]f[j−w[i]]f[j−w[i]]f[j−w[i](旧データよ)に依存するため、順方向列挙するとf[j−w[i]]f[j−w[i]]f[j−w[i]]が既に新データで上書きされており、既にアイテムiが選択されている可能性がある!(f[i][j]f[i][j]f[i][j]f[i][j]は、前のiつのアイテムから選択することを忘れないでください)
すなわち,元のf[i−1][j−w[i]]f[i−1][j−w[i]]f[i−1][j−w[i]]f[i−1][j−w[i]]は既に覆われており,現在はf[i][j−w[i]]f[i][j−w[i]]f[i][j−w[i]]f[i][j−w[i]]f[i][j−w[i]]f[i][j−w[i]]f[i][j−w[このときすでにアイテムi i i iが選ばれている可能性が高いので、今回もアイテムi i iが選ばれたら、アイテムi i i iが2回選ばれ、0-1リュックサックの制限に違反します!
そのため、0-1リュックサックの制限に背かないように、逆さに列挙しなければなりません.
最適化された疑似コードは次のとおりです.

for 1...n
    for s...w[i]
           f[j]=max{
     f[j-w[i]]+v[i],f[j]}

例題:

     

       ，             ，                  。       ，       ：“            ，    ，    ，     N    ”。            ，           ，          N 。  ，              ，  5 ：   1~5  ， 5    。                 （     ）。       N （    N ）    ，                    。

  j       v[j]，    w[j]，    k   ，     j1...jk，       ：v[j1]*w[j1]+..+v[jk]*w[jk]。

                  。

【    】
    1 ，      N,M，       ：（  n（n<30000）     ，m(m<25)          。）

  2    m+1 ， j       j-1        ，   2     v，p
（  v         （v≤10000），p          （1~5）） 

【    】
         ，                          （<100000000）。

【    】
1000 5
800 2
400 5
300 5
400 3
200 2
【    】
3900

コード:

#include
#include 
using namespace std;
struct thing {
     
   int v,p;
} want[30];
long long c[10010],d[10010];
int main() {
     
   int n,m;
   cin>>n>>m;
   for(int i=1; i<=m; i++) {
     
       cin>>want[i].v>>want[i].p;
   }
   for(int i=1; i<=m; i++) {
     
       for(int j=n; j>=want[i].v; j--) {
     
           c[j]=max(c[j],c[j-want[i].v]+want[i].v*want[i].p);
       }
   }
   cout << c[n] << endl;
   return 0;
}

数回のリュックサックを選べます–完全リュックサック
問題の説明:
N N N個の物品と1個の容量がS S Sのリュックサックがあって、i i i番目の物品の重量はw[i]w[i]w[i]で、価値はv[i]v[i]v[i]です.それぞれの品物に無限のものがあり、分割できず、リュックサックの容量を超えない前提の下で、どのようにリュックサックの総価値を最大にすることができるかを聞く.
この問題は0-1リュックの問題と似ているので、0-1リュックの上で一定の修正をすればいいです.
考えてみてください.0-1リュックサックはどこで重複選択の可能性を阻止しましたか.
もちろんj j jのサイクルというところです!
では、私たちは直接j j jのサイクルという場所を正序(繰り返し物を入れる可能性があり、ちょうど要求を満たす)に変えればいいのではないでしょうか.
完全なコードは以下の通りです(例題QQQQが見つかりません)

#include
#include
using namespace std;
struct thing {
      
   int v,p;
} want[30];
long long c[10010];
int main() {
      
    int n,m,;    
    cin>>n>>m;    
    for(int i=1; i<=m; i++) {
      
          cin>>want[i].v>>want[i].p;    
    }    
    for(int i=1; i<=m; i++) {
             
        for(int j=want[i].v;j<=n; j++) {
               
            c[j]=max(c[j],c[j-want[i].v]+want[i].p);       
          }   
     }    
     cout << c[n] << endl; 
     return 0;
}

数に上限のあるリュック-多重リュック
问题补充:N N N个の物品と1つの容量がS S Sのリュックサックがあって、i i i番目の物品の重量はw[i]w[i]w[i]w[i]で、価値はv[i]v[i]v[i]で、上限はc[i]c[i]c[i]c[i]です.分割不可、リュックの容量を超えない前提の下で、どのようにリュックの総価値を最大にすることができるかを聞きます.
この問題は0-1リュックの問題にも似ているので、0-1リュックの上で一定の修正をすることもできます.
0から上限までのアイテムの数を列挙するループを直接追加することができます.擬似コードは次のとおりです.

for 1...n 
   for s...w[i]  
       for 0...c[i]
         if j>=w[i]*k
          f[j]=max{
     f[j-w[i]*k]+v[i]*k,f[j]}

例題:

   

                       ，           ，             。               ，            。
【    】
      n（≤500），m（≤6000），             。
   n ，     v，p，s，        ，            ，  v≤100，p≤1000，s≤10。
【    】
   ，              。
【    】
5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1
【    】
1040

#include
#include
using namespace std;
struct thing {
      
  int v,p,s;
} want[30];
long long c[10010];
int main() {
      
  int n,m;       
  cin>>n>>m;      
  for(int i=1; i<=m; i++) {
     
             cin>>want[i].v>>want[i].p>>want[i].s;        
  }        
  for(int i=1; i<=n; i++) {
      
     for(int j=m;j>=want[i].v; j--) {
     
         for(int k=0;k<=want[i].s; k++){
     
              if(j >=k*want[i].v)
                 c[j]=max(c[j],c[j-k*want[i].v]+k*want[i].p);      
        }          
     }       
  }          
  cout << c[m] << endl;      
  return 0;
}

付:0-1リュックサックの空間と時間が最も優れているコード

#include 
#include 
using namespace std;
int main(){
     
    int n,s,f[100],w,v;
    cin>>n>>s;
    for(int i = 1;i <= n;i++)
        cin>>w>>v;
        for(int j = s; j >= w[i]; j--)
            f[j] = max(f[j], f[j-w]+v);
    cout<<f[s]<<endl;
    return 0;
}

超大礼包https://www.luogu.com.cn/discuss/show/263072