2022/02/28,今天回来更新一下,心血来潮重写了一遍,发现一直提交不过。为啥呢?
原因出在对s进行拆分,想的比较简单while(c<=s)c*2;
比如说如果是259,会多出来一个数512,这样就会多了许多的情况。(6分50秒)
实际上只能拆到256,剩下的3(259-256)。作为最终的整体,这样虽然有重复情况(如2+1和3)。
但是保证了不会有不存在的情况。
额外的知识点。如果用最少的某进制数表示一个数呢,log_b n+1(上取整),即可
- 首先关于N的设定,因为log2(2000)<11,所以最多的商品数量应小于11*2000
- 输入时将ts(假设其小于63)做拆分,拆成1 2 4 8 16 n-(1+2+4+8+16),对应的商品vol和weight分别为ts ×(1 2 4 8 16 n-(1+2+4+8+16)),tw ×(1 2 4 8 16 n-(1+2+4+8+16)),将其导入idx下标的位置即可
- 最后按照正常的01背包做就好啦
C++ 代码
#include<iostream>
using namespace std;
const int N = 22010;
int v[N],w[N];
int dp[2010];
int main(){
int num,vol;
cin>>num>>vol;
int index = 1;
int tv,tw,ts;
for(int i=1;i<=num;i++){
cin>>tv>>tw>>ts;
for(int j=1;ts-j>0;j*=2){
v[index] = tv*j;
w[index] = tw*j;
ts-=j;
index++;
}
if(ts>0){
v[index] = tv*ts;
w[index] = tw*ts;
ts = 0;
index++;
}
}
for(int i=1;i<=index-1;i++){
for(int j=vol;j>=0;j--){
if(j-v[i]>=0)dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[vol];
return 0;
}