Powered by:AB_IN 局外人
我太菜了，現在才學
看的入門班的錄播，大約明白了，
是物品的個數，是背包的容量，代表第物品的費用，代表第物品的價值，
先給出最原始推出來的式子
dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
什么意思呢？
表示前件物品恰好放入一個容量為的背包里可以獲得的最大價值，
- 就表示，不選第個物品，就讓前個物品去組成容量為的背包，
- 就表示，選第個物品，讓的背包正好加上第個物品，容量不就正好為了嘛，
- 這兩個取最大值即可，
但問題是這樣太浪費空間了，可以通過式子看出只和有關，也就是和上一行，再加上是從到的，也就是前面一些行就沒有用了，會很浪費空間，
所以便有了01滾動和就地滾動，
-
01滾動，顧名思義，就是兩行之間的相互利用，一行記錄前一行的值，另一行記錄當前行的值，
-
就地滾動，顧名思義，就是用一個一維陣列，之前的狀態和當前的狀態都在同一個陣列里，
但如果從到的話，會出現，一個物品會被算多次，因為會一直往右走到，比如一個放進去了，往右走，會走到剛剛放進去的那個狀態，原先放進去的會被再放一遍，顯然這樣是錯的，因為上一行狀態和這一行狀態混了，
那該怎么辦呢？
讓從右往左走即可，上一行的狀態在的左邊，這一行的狀態在的右邊，
代碼孕育而生，
for(int i=1;i<=n;i++){
for(int j=v;j>=c[i];j--){
dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
}
}
愛玩游戲的Tom
#include<bits/stdc++.h>
using namespace std;
const int N=50005;
typedef long long ll;
ll n,m,dp[N],c[N],w[N];
int main()
{
cin>>n>>m;
for(ll i=1;i<=n;i++){
cin>>c[i]>>w[i];
}
for(ll i=1;i<=n;i++){
for(ll j=m;j>=c[i];j--){
dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
}
}
cout<<dp[m]<<endl;
return 0;
}
完結，
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/5838.html
標籤：其他
上一篇：演算法：給一個二叉樹，每個節點都有權值，你可以從這個樹的節點往下走，到任意節點停止，你得到的分數是走過路徑上的權值的異或和