【SSL_1376】完全バックパック(DP)

完全リュックサック
タイトル
n種類の物品が設けられており、各物品には重量と価値がある.しかし、それぞれの品物の数は無限で、同時に1つのリュックサックがあって、最大積載重量はMで、今n種類の品物の中からいくつかのもの(同じ品物は何度も選択することができます)を選んで、その重量の和がMに等しくないようにして、価値の和は最大です.
Input
1行目:2つの整数、M(リュックサック容量、M<=200)とN(物品数、N<=30);第2…N+1行:1行あたり2つの整数Wi,Uiは、各物品の重量と価値を表す.
Output
1行のみ、1つの数で、最大の総価値を表します.
Sample Input
12 4 2 1 3 3 4 5 7 9
Sample Output
15
問題解
この問題は完全なリュックの問題で、(くだらない話)だから容量を列挙する時01リュックのように大きいから小さいまでではなく、小さいから大きいまで列挙して、その品物は無限なので、前の状態の記録を使う必要があります.f[i][j]は、容量がjのときに前のi個の物品が達成できる最大の価値とし、f初期は0、1<=i<=n、a[i]<=j<=v、f[i][j]=max(f[i-1][j],f[i][j-a[i]+b[i])a配列が重量を表し、b配列が価値を表し、jがa[i]から始まるのは、a[i]以前の容量がa[i]に収まらないためである.状態遷移方程式は、f[i][j]が物品iを選択しないか、選択するか、選択すると最大価値は、容量が現在の容量から選択された物品の重量を減らすときに、前のi個の物品が達成できる最大価値であることを意味する.
コード#コード#

#include
#include 
#include
#include
using namespace std;
long long n,a[201],s,ans,f[201][201],v,b[201];
void dp(){
	for(int i=1;i<=n;i++){//    
		scanf("%d%d",&a[i],&b[i]);
		for(int j=a[i];j<=v;j++){//    
			f[i][j]=max(f[i-1][j],(f[i][j-a[i]]+b[i]));//       
			ans=max(ans,f[i][j]);//       
		}
	}
}
void in(){
	cin>>v>>n;
}
int main(){
	in();
	dp();
	cout<<ans;
}

もちろん,この問題は2次元配列の代わりに1次元スクロール配列を用いて空間を減らす最適化も可能である.前のf配列はi-1までしか使えないので、前のf配列は使えないので、1次元配列しか使いません.

#include
#include 
#include
#include
using namespace std;
long long n,a[201],s,ans,f[201],v,b[201];
void dp(){
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i],&b[i]);
		for(int j=a[i];j<=v;j++){
			f[j]=max(f[j],(f[j-a[i]]+b[i]));//             
		}
	}
}
void in(){
	cin>>v>>n;
}
int main(){
	in();
	dp();
	cout<<f[v];
}